Submission #1187520
Source Code Expand
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iterator>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
int x, y, z, n, m;
vector<pair<int, lli>> t;
vector<vector<vector<lli>>> dp;
int main(void){
scanf("%d%d%d", &x, &y, &n); z = x + y; m = min(x, n);
t.resize(n+1);
reg(i, 1, n) scanf("%d%lld", &t[i].fir, &t[i].sec);
vector<lli> zvl(n+1, 0); vector<lli> tvl(n+1, -1); tvl[0] = 0;
vector<vector<lli>> zvvl(m+1, zvl); vector<vector<lli>> tvvl(m+1, tvl); tvvl[0] = zvl;
dp.assign(z+1, tvvl);
dp[0] = zvvl;
rep(j, n){
rep(k, m+1){
rep(i, z+1){
if(i+t[j+1].fir <= z && k+1 <= m && dp[i+t[j+1].fir][k+1][j+1] < dp[i][k][j]+t[j+1].sec) dp[i+t[j+1].fir][k+1][j+1] = dp[i][k][j]+t[j+1].sec;
dp[i][k][j+1] = max(dp[i][k][j+1], dp[i][k][j]);
}
}
}
lli ans = 0;
rep(k, m+1){
rep(i, z+1){
ans = max(ans, dp[i][k][n]);
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 最高のトッピングにしような |
User |
ktyshmt |
Language |
C++14 (GCC 5.4.1) |
Score |
30 |
Code Size |
1612 Byte |
Status |
TLE |
Exec Time |
2131 ms |
Memory |
432776 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:36:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &n); z = x + y; m = min(x, n);
^
./Main.cpp:38:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
reg(i, 1, n) scanf("%d%lld", &t[i].fir, &t[i].sec);
^
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
0 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask0-sample04.txt |
Subtask1 |
subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask0-sample04.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt |
Subtask2 |
subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask0-sample04.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0-sample01.txt |
AC |
1 ms |
256 KB |
subtask0-sample02.txt |
AC |
1 ms |
256 KB |
subtask0-sample03.txt |
AC |
1 ms |
256 KB |
subtask0-sample04.txt |
AC |
1 ms |
256 KB |
subtask1-01.txt |
AC |
1 ms |
256 KB |
subtask1-02.txt |
AC |
1 ms |
256 KB |
subtask1-03.txt |
AC |
1 ms |
256 KB |
subtask1-04.txt |
AC |
1 ms |
256 KB |
subtask1-05.txt |
AC |
1 ms |
256 KB |
subtask1-06.txt |
AC |
1 ms |
384 KB |
subtask1-07.txt |
AC |
1 ms |
384 KB |
subtask1-08.txt |
AC |
1 ms |
256 KB |
subtask1-09.txt |
AC |
1 ms |
384 KB |
subtask1-10.txt |
AC |
1 ms |
384 KB |
subtask1-11.txt |
AC |
1 ms |
384 KB |
subtask1-12.txt |
AC |
2 ms |
640 KB |
subtask1-13.txt |
AC |
2 ms |
896 KB |
subtask1-14.txt |
AC |
1 ms |
256 KB |
subtask1-15.txt |
AC |
1 ms |
256 KB |
subtask1-16.txt |
AC |
1 ms |
256 KB |
subtask1-17.txt |
AC |
3 ms |
1408 KB |
subtask1-18.txt |
AC |
3 ms |
1408 KB |
subtask1-19.txt |
AC |
3 ms |
1408 KB |
subtask1-20.txt |
AC |
4 ms |
2560 KB |
subtask1-21.txt |
AC |
4 ms |
2560 KB |
subtask1-22.txt |
AC |
4 ms |
2560 KB |
subtask1-23.txt |
AC |
4 ms |
2560 KB |
subtask1-24.txt |
AC |
4 ms |
2560 KB |
subtask1-25.txt |
AC |
4 ms |
2560 KB |
subtask2-01.txt |
AC |
3 ms |
1280 KB |
subtask2-02.txt |
AC |
3 ms |
1536 KB |
subtask2-03.txt |
AC |
2 ms |
768 KB |
subtask2-04.txt |
AC |
65 ms |
22528 KB |
subtask2-05.txt |
AC |
27 ms |
12800 KB |
subtask2-06.txt |
AC |
144 ms |
26368 KB |
subtask2-07.txt |
AC |
57 ms |
13568 KB |
subtask2-08.txt |
AC |
461 ms |
62080 KB |
subtask2-09.txt |
AC |
45 ms |
20992 KB |
subtask2-10.txt |
AC |
86 ms |
35712 KB |
subtask2-11.txt |
AC |
121 ms |
16384 KB |
subtask2-12.txt |
AC |
231 ms |
37120 KB |
subtask2-13.txt |
AC |
1930 ms |
211328 KB |
subtask2-14.txt |
TLE |
2131 ms |
432768 KB |
subtask2-15.txt |
AC |
1634 ms |
217600 KB |
subtask2-16.txt |
AC |
1982 ms |
217600 KB |
subtask2-17.txt |
AC |
1628 ms |
217600 KB |
subtask2-18.txt |
AC |
3 ms |
1664 KB |
subtask2-19.txt |
AC |
3 ms |
1664 KB |
subtask2-20.txt |
TLE |
2129 ms |
396928 KB |
subtask2-21.txt |
TLE |
2129 ms |
432776 KB |
subtask2-22.txt |
AC |
1985 ms |
217600 KB |
subtask2-23.txt |
TLE |
2122 ms |
289280 KB |
subtask2-24.txt |
TLE |
2131 ms |
432768 KB |
subtask2-25.txt |
TLE |
2131 ms |
432768 KB |