fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ____AnhKietSS____ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define NamDinh signed
  5. #define ll long long
  6. #define ii pair<int,int>
  7. #define foru(i,d,c) for(int i=(d);i<=(c);i++)
  8. #define ford(i,d,c) for(int i=(d);i>=(c);i--)
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12. #define pf push_front
  13. #define MOD 1000000007
  14. #define inf 0x3f
  15. #define INF 4557430888798830399LL
  16.  
  17. using namespace std;
  18.  
  19. struct State
  20. {
  21.     ll cost;
  22.     int u;
  23.     int p;
  24.     bool is_free;
  25. };
  26.  
  27. ll solveSubtaskN40(int n,ll k,vector<ll>&a,vector<ll>&b)
  28. {
  29.     ll z=INF;
  30.  
  31.     foru(x,1,n)
  32.     {
  33.         vector<bool> c(n+1,false);
  34.         vector<bool> d(n+1,false);
  35.         vector<ll> e(n+1,0);
  36.  
  37.         c[x]=true;
  38.         d[x]=true;
  39.         e[x]=a[x];
  40.  
  41.         ll f=0;
  42.         bool g=true;
  43.  
  44.         foru(i,1,n-1)
  45.         {
  46.             int u=-1;
  47.             int v=-1;
  48.             ll w=INF;
  49.             bool t=false;
  50.  
  51.             foru(j,1,n)
  52.             {
  53.                 if(c[j])
  54.                 {
  55.                     continue;
  56.                 }
  57.  
  58.                 foru(p,1,n)
  59.                 {
  60.                     if(!c[p])
  61.                     {
  62.                         continue;
  63.                     }
  64.  
  65.                     ll q=k*max(0LL,e[p]+1-a[j]);
  66.  
  67.                     if(d[p])
  68.                     {
  69.                         if(q<w)
  70.                         {
  71.                             w=q;
  72.                             u=j;
  73.                             v=p;
  74.                             t=true;
  75.                         }
  76.                     }
  77.  
  78.                     q+=b[p];
  79.  
  80.                     if(q<w)
  81.                     {
  82.                         w=q;
  83.                         u=j;
  84.                         v=p;
  85.                         t=false;
  86.                     }
  87.                 }
  88.             }
  89.  
  90.             if(u==-1)
  91.             {
  92.                 g=false;
  93.                 break;
  94.             }
  95.  
  96.             c[u]=true;
  97.             d[u]=true;
  98.             e[u]=max(a[u],e[v]+1);
  99.  
  100.             f+=w;
  101.  
  102.             if(t)
  103.             {
  104.                 d[v]=false;
  105.             }
  106.         }
  107.  
  108.         if(g)
  109.         {
  110.             z=min(z,f);
  111.         }
  112.     }
  113.  
  114.     return z;
  115. }
  116.  
  117. NamDinh main()
  118. {
  119.     ____AnhKietSS____
  120.  
  121.  
  122.  
  123.     int n;
  124.     ll k;
  125.  
  126.     cin>>n>>k;
  127.  
  128.     vector<ll>a(n+1),b(n+1);
  129.  
  130.     foru(i,1,n)
  131.     {
  132.         cin>>a[i]>>b[i];
  133.     }
  134.  
  135.     if(n==1)
  136.     {
  137.         cout<<0<<"\n";
  138.         return 0;
  139.     }
  140.  
  141.     cout<<solveSubtaskN40(n,k,a,b)<<"\n";
  142.  
  143.     return 0;
  144. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5 2
0 6
1 1
 0 5
2 1
1 2
stdout
copy 
8
https://ideone.com/7S2HG5
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!