# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
58983 | 2018-07-20T01:31:09 Z | red1108 | None (KOI17_cook) | C++17 | 8 ms | 2644 KB |
#include <vector> #include <stdio.h> #include <deque> using namespace std; typedef long long ll; const long long inf=2100000000; vector<vector<int>> input,sum; vector<long long> dp[3010]; struct DATA{ long long value; long long before; }mindp[6010][3]; deque<pair<long long,long long>> dq[3010]; ll n, m, row, limit, change, cant[3010]; ll getmin(ll i,ll j) { if(i<row) return (-1)*change; if(mindp[i][0].before!=cant[j]&&mindp[i][0].before!=j) return mindp[i][0].value; else if(mindp[i][1].before!=cant[j]&&mindp[i][1].before!=j) return mindp[i][1].value; else if(mindp[i][2].before!=cant[j]&&mindp[i][2].before!=j) return mindp[i][2].value; } void gang(ll i, ll j,ll bac) { if(mindp[i][0].value==0)mindp[i][0].value=mindp[i][1].value=mindp[i][2].value=inf*inf; if(j<1) return; if(mindp[i][0].value>=j) { mindp[i][2]=mindp[i][1]; mindp[i][1]=mindp[i][0]; mindp[i][0].value=j; mindp[i][0].before=bac; } else if(mindp[i][1].value>=j) { mindp[i][2]=mindp[i][1]; mindp[i][1].value=j; mindp[i][1].before=bac; } else if(mindp[i][2].value>=j) { mindp[i][2].value=j; mindp[i][2].before=bac; } } int main() { ll i, j, ina; scanf("%lld %lld %lld %lld %lld", &n, &m, &row, &limit, &change); input.push_back(vector<int>{0}); sum.push_back(vector<int>{0}); for(i=1;i<=n;i++) { input.push_back(vector<int>{0}); sum.push_back(vector<int>{0}); dp[i].push_back(0); for(j=1;j<=m;j++) { scanf("%lld",&ina); input[i].push_back(ina); sum[i].push_back(sum[i][j-1]+ina); dp[i].push_back(0); } for(j=1;j<=m;j++) {sum[i].push_back(sum[i][sum[i].size()-1]);input[i].push_back(0);dp[i].push_back(0);} } for(i=1;i<=n;i++) scanf("%lld", &cant[i]); for(i=row;i<=m+row-1;i++) { if(i-row<row&&i>limit){gang(i,inf*inf,inf*inf);for(j=1;j<=n;j++) dp[j][i]=inf*inf;continue;} for(j=1;j<=n;j++) { while(!dq[j].empty()&&dq[j].front().second<i-limit+1) dq[j].pop_front(); pair<int,int> newput={getmin(i-row,j)+change,i-row+1}; if(i-row>=row||i<=limit){ if(i-row<row&&i<=limit) newput.second=1; while(!dq[j].empty()&&(dq[j].back().first+sum[j][i]-sum[j][dq[j].back().second-1]>=newput.first+sum[j][i]-sum[j][i-row]||dq[j].back().second<i-limit+1)) dq[j].pop_back(); dq[j].push_back(newput); } if(dq[j].empty())dp[j][i]=inf*inf; else dp[j][i]=dq[j].front().first+sum[j][i]-sum[j][dq[j].front().second-1]; gang(i,dp[j][i],j); } } ll ans=inf*inf; for(i=1;i<=n;i++) { for(j=m;j<=m+row-1;j++) { ans=dp[i][j]<ans&&dp[i][j]>0?dp[i][j]:ans; } } printf("%lld",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2424 KB | Output is correct |
2 | Correct | 6 ms | 2532 KB | Output is correct |
3 | Correct | 6 ms | 2568 KB | Output is correct |
4 | Correct | 5 ms | 2568 KB | Output is correct |
5 | Incorrect | 8 ms | 2644 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2424 KB | Output is correct |
2 | Correct | 6 ms | 2532 KB | Output is correct |
3 | Correct | 6 ms | 2568 KB | Output is correct |
4 | Correct | 5 ms | 2568 KB | Output is correct |
5 | Incorrect | 8 ms | 2644 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2424 KB | Output is correct |
2 | Correct | 6 ms | 2532 KB | Output is correct |
3 | Correct | 6 ms | 2568 KB | Output is correct |
4 | Correct | 5 ms | 2568 KB | Output is correct |
5 | Incorrect | 8 ms | 2644 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2424 KB | Output is correct |
2 | Correct | 6 ms | 2532 KB | Output is correct |
3 | Correct | 6 ms | 2568 KB | Output is correct |
4 | Correct | 5 ms | 2568 KB | Output is correct |
5 | Incorrect | 8 ms | 2644 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2424 KB | Output is correct |
2 | Correct | 6 ms | 2532 KB | Output is correct |
3 | Correct | 6 ms | 2568 KB | Output is correct |
4 | Correct | 5 ms | 2568 KB | Output is correct |
5 | Incorrect | 8 ms | 2644 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |