| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130119 |
2019-07-14T04:01:14 Z |
aer0park |
None (KOI17_cook) |
C++14 |
|
3 ms |
1272 KB |
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
ll n,m,s,e,t,mnc[3005],anw=1e15;
ll dp[3005][3005]; // i번쨰 학원에서 j번 강좌까지를 끝마쳤을때 최소비용 즉 무조건 학원바꿈
int ck[3005][3005],x[3005],c[3005][3005],pc[3005][3005]; // c:i번쨰 학원에서 j번강좌를 들을 경우 비용 pc:i번쨰 학원에서 j번강좌까지를 들을 경우 비용
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m>>s>>e>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>c[i][j],pc[i][j]=pc[i][j-1]+c[i][j];
for(int i=1;i<=n;i++)
cin>>x[i];
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
dp[i][j]=1e15;
for(int i=1;i<=n;i++)
dp[i][0]=-t;
for(int i=0;i<=m;i++)
{
ll nw=min(m,i+s);
if(i&&i+s<=m)
{
for(int j=1;j<=n;j++)
if(ck[j][nw-1])
ck[j][nw]=ck[j][nw-1]-1,dp[j][nw]=dp[j][nw-1]+c[j][nw];
}
vector<pi> ar;
for(int j=1;j<=n;j++)
ar.push_back({dp[j][i]+t,j});
sort(ar.begin(),ar.end());
for(int j=1;j<=n;j++)
{
ll k=0;
while(ar[k].s==x[j]||ar[k].s==j)
k++;
mnc[j]=ar[k].f;
}
for(int j=1;j<=n;j++)
if(dp[j][nw]>mnc[j]+pc[j][nw]-pc[j][i])
dp[j][nw]=mnc[j]+pc[j][nw]-pc[j][i],ck[j][nw]=e-s;
}
for(int i=1;i<=n;i++)
anw=min(anw,dp[i][m]);
cout<<anw;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 4 |
Correct |
3 ms |
888 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
1248 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 4 |
Correct |
3 ms |
888 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
1248 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 4 |
Correct |
3 ms |
888 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
1248 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 4 |
Correct |
3 ms |
888 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
1248 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 4 |
Correct |
3 ms |
888 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
1248 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
