fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define el cout<<"\n"
  3. #define SZ(x) (x).begin(),(x).end()
  4. #define BIT(x,i) (((x)>>(i))&1LL)
  5. #define int long long
  6. #define MASK(i)  (1LL<<(i))
  7. using namespace std;
  8. typedef long long ll;
  9. const int N=1e5 + 7;
  10. ll INF=1e18+7;
  11. int a[N];
  12. ll C[105][105],color[505][505],f[N];
  13. ll dpfull[N][105],pre[N][105];
  14. int n,T,K;
  15.  
  16. void subfull(){
  17.     for(int i=1;i<=n;i++){
  18.         for(int j=1;j<=T;j++){
  19.             dpfull[i][j]=INF;
  20.         }
  21.         f[i]=INF;
  22.     }
  23.     for(int i=1;i<=n;i++){
  24.         for(int j=1;j<=T;j++){
  25.             pre[i][j]=pre[i-1][j]+C[a[i]][j];
  26.         }
  27.     }
  28.     for(int i=K;i<=n;i++){
  29.         for(int j=1;j<=T;j++){
  30.             dpfull[i][j]=min(dpfull[i-1][j]+C[a[i]][j],f[i-K]+pre[i][j]-pre[i-K][j]);
  31.             f[i]=min(dpfull[i][j],f[i]);
  32.         }
  33.     }
  34.     cout<<f[n];
  35. }
  36. void ip(){
  37.     cin>>n>>K>>T;
  38.     for(int i=1;i<=n;i++){
  39.         cin>>a[i];
  40.     }
  41.     for(int i=1;i<=T;i++){
  42.         for(int j=1;j<=T;j++){
  43.             cin>>C[i][j];
  44.             if(i==j) C[i][j]=0;
  45.         }
  46.     }
  47.     for(int i=1;i<=T;i++){
  48.         for(int j=1;j<=T;j++){
  49.             for(int k=1;k<=T;k++){
  50.                 C[i][j]=min(C[i][j],C[i][k]+C[k][j]);
  51.             }
  52.         }
  53.     }
  54.  
  55.     subfull();
  56. }
  57. signed main(){
  58. //    freopen("test.inp","r",stdin);
  59. //    freopen("test.out","w",stdout);
  60.     ios_base::sync_with_stdio(0);
  61.     cin.tie(0);cout.tie(0);
  62.     ip();
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QfvbZl
language:
C++ (gcc 8.3)
created:
4 days 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!