oj.uz

Submission #265483

# Submission time Handle Problem Language Result Execution time Memory
265483 2020-08-14T22:05:21 Z kimbj0709 Popeala (CEOI16_popeala) C++14
100 / 100
 389 ms 9980 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 20050
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,t,s;
    cin >> n >> t >> s;
    vector<int> points;
    int input1;
    char input;
    points.push_back(0);
    for(int i=0;i<t;i++){
        cin >> input1;
        points.push_back(input1);
        points[i+1] += points[i];
    }
    int last[t+5][n+1];
    memset(last,0,sizeof(last));
    for(int i=0;i<n;i++){
      for(int j=1;j<=t;j++){
        cin >> input;
        if(input=='0'){
          last[j][i] = j;
        }
        else{
          last[j][i] = last[j-1][i];
        }
      }
    }
    for(int i=0;i<=t;i++){
      last[i][n] = i;
      sort(last[i],last[i]+n+1);
    }
    for(int i=0;i<=t;i++){
      for(int j=0;j<=n;j++){
        //cout << last[i][j] << " ";
      }
      //cout << endl;
    }
    vector<int> dp(maxn,INT_MAX);
    dp[0] = 0;
    vector<int> mi(n+5,INT_MAX);
    for(int i=0;i<s;i++){
      vector<int> temp(maxn,INT_MAX);
      for(int j=0;j<=n;j++){
        mi[j] = INT_MAX;
      }
      for(int j=1;j<=t;j++){
        for(int k=0;k<=n;k++){
          for(int p=last[j-1][k];p<last[j][k];p++){
            mi[k] = min(mi[k],dp[p]-points[p]*k);
          }
          //cout << mi[k] << "--\n";
          temp[j] = min(temp[j],mi[k]+points[j]*k);
        }
      }
      //if(i!=0) continue;
      /*for(int j=0;j<=t;j++){
        cout << temp[j] << ' ';
      }
      cout << endl;*/
      cout << temp[t] << "\n";
      dp = temp;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 896 KB Output is correct
2 Correct 11 ms 896 KB Output is correct
3 Correct 12 ms 916 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1536 KB Output is correct
2 Correct 70 ms 2048 KB Output is correct
3 Correct 85 ms 2560 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 12 ms 896 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 12 ms 916 KB Output is correct
6 Correct 50 ms 1536 KB Output is correct
7 Correct 70 ms 2048 KB Output is correct
8 Correct 85 ms 2560 KB Output is correct
9 Correct 114 ms 3712 KB Output is correct
10 Correct 179 ms 4736 KB Output is correct
11 Correct 312 ms 9688 KB Output is correct
12 Correct 328 ms 9976 KB Output is correct
13 Correct 389 ms 9976 KB Output is correct
14 Correct 389 ms 9980 KB Output is correct
15 Correct 388 ms 9976 KB Output is correct