Submission #265483

#	Time	Username	Problem	Language	Result	Execution time	Memory
265483		kimbj0709	Popeala (CEOI16_popeala)	C++14	100 / 100	389 ms	9980 KiB

popeala

#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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74