Submission #1059972
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
int main() {
int n, m, y, z;
scanf("%d %d %d %d", &n, &m, &y, &z);
map<char, int> mp;
vi point(m);
rep (i, m) {
char tmp;
scanf(" %c", &tmp);
mp[tmp] = i;
scanf("%d", &point[i]);
}
vi b(n);
rep (i, n) {
char tmp;
scanf(" %c", &tmp);
b[i] = mp[tmp];
}
fflush(stdin);
vvi dp;
dp.assign((1 << m), vi(m+1, INT_MIN));
dp[0][m] = 0;
vvi tmp;
FOR (i, 0, n) {
tmp.assign((1 << m), vi(m+1, INT_MIN));
rep (j, (1 << m)) {
int new_j = (j | (1 << b[i]));
bool complete_flag = false;
if (j != (1 << m) - 1 && new_j == (1 << m) - 1) {
complete_flag = true;
}
rep (k, m+1) {
if (dp[j][k] != INT_MIN) {
tmp[j][k] = max(tmp[j][k], dp[j][k]);
int new_point = dp[j][k] + point[b[i]];
if (k == b[i]) {
new_point += y;
}
if (complete_flag) {
new_point += z;
}
tmp[new_j][b[i]] = max(tmp[new_j][b[i]], new_point);
}
}
}
dp = tmp;
}
int ans = 0;
rep (j, (1 << m)) {
rep (k, m+1) {
ans = max(ans, dp[j][k]);
}
}
printf("%d\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 積み上げパズル |
User |
tspcx |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
2131 Byte |
Status |
AC |
Exec Time |
31 ms |
Memory |
928 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:40:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &n, &m, &y, &z);
^
./Main.cpp:45:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &tmp);
^
./Main.cpp:47:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &point[i]);
^
./Main.cpp:52:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &tmp);
^
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_rand_00.txt, 01_rand_01.txt, 01_rand_02.txt, 01_rand_03.txt, 01_rand_04.txt, 01_rand_05.txt, 01_rand_06.txt, 01_rand_07.txt, 01_rand_08.txt, 01_rand_09.txt, 01_rand_10.txt, 01_rand_11.txt, 01_rand_12.txt, 01_rand_13.txt, 01_rand_14.txt, 01_rand_15.txt, 01_rand_16.txt, 01_rand_17.txt, 01_rand_18.txt, 01_rand_19.txt, 02_connect_00.txt, 02_connect_01.txt, 02_connect_02.txt, 02_connect_03.txt, 02_connect_04.txt, 02_connect_05.txt, 02_connect_06.txt, 02_connect_07.txt, 02_connect_08.txt, 02_connect_09.txt, 02_connect_10.txt, 02_connect_11.txt, 02_connect_12.txt, 02_connect_13.txt, 02_connect_14.txt, 02_connect_15.txt, 02_connect_16.txt, 02_connect_17.txt, 02_connect_18.txt, 02_connect_19.txt, 02_connect_20.txt, 02_connect_21.txt, 02_connect_22.txt, 02_connect_23.txt, 02_connect_24.txt, 02_connect_25.txt, 02_connect_26.txt, 02_connect_27.txt, 02_connect_28.txt, 02_connect_29.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample_01.txt |
AC |
20 ms |
800 KB |
00_sample_02.txt |
AC |
19 ms |
800 KB |
00_sample_03.txt |
AC |
19 ms |
800 KB |
00_sample_04.txt |
AC |
17 ms |
796 KB |
01_rand_00.txt |
AC |
19 ms |
800 KB |
01_rand_01.txt |
AC |
17 ms |
800 KB |
01_rand_02.txt |
AC |
18 ms |
792 KB |
01_rand_03.txt |
AC |
19 ms |
800 KB |
01_rand_04.txt |
AC |
17 ms |
800 KB |
01_rand_05.txt |
AC |
19 ms |
800 KB |
01_rand_06.txt |
AC |
19 ms |
796 KB |
01_rand_07.txt |
AC |
17 ms |
800 KB |
01_rand_08.txt |
AC |
20 ms |
924 KB |
01_rand_09.txt |
AC |
18 ms |
924 KB |
01_rand_10.txt |
AC |
19 ms |
796 KB |
01_rand_11.txt |
AC |
17 ms |
800 KB |
01_rand_12.txt |
AC |
19 ms |
796 KB |
01_rand_13.txt |
AC |
19 ms |
844 KB |
01_rand_14.txt |
AC |
19 ms |
804 KB |
01_rand_15.txt |
AC |
19 ms |
800 KB |
01_rand_16.txt |
AC |
19 ms |
796 KB |
01_rand_17.txt |
AC |
19 ms |
796 KB |
01_rand_18.txt |
AC |
19 ms |
924 KB |
01_rand_19.txt |
AC |
19 ms |
924 KB |
02_connect_00.txt |
AC |
19 ms |
796 KB |
02_connect_01.txt |
AC |
19 ms |
800 KB |
02_connect_02.txt |
AC |
18 ms |
796 KB |
02_connect_03.txt |
AC |
19 ms |
800 KB |
02_connect_04.txt |
AC |
19 ms |
800 KB |
02_connect_05.txt |
AC |
18 ms |
800 KB |
02_connect_06.txt |
AC |
21 ms |
796 KB |
02_connect_07.txt |
AC |
19 ms |
800 KB |
02_connect_08.txt |
AC |
24 ms |
924 KB |
02_connect_09.txt |
AC |
19 ms |
920 KB |
02_connect_10.txt |
AC |
19 ms |
800 KB |
02_connect_11.txt |
AC |
17 ms |
800 KB |
02_connect_12.txt |
AC |
19 ms |
792 KB |
02_connect_13.txt |
AC |
19 ms |
792 KB |
02_connect_14.txt |
AC |
19 ms |
792 KB |
02_connect_15.txt |
AC |
19 ms |
924 KB |
02_connect_16.txt |
AC |
21 ms |
796 KB |
02_connect_17.txt |
AC |
19 ms |
800 KB |
02_connect_18.txt |
AC |
19 ms |
928 KB |
02_connect_19.txt |
AC |
21 ms |
924 KB |
02_connect_20.txt |
AC |
18 ms |
916 KB |
02_connect_21.txt |
AC |
19 ms |
800 KB |
02_connect_22.txt |
AC |
19 ms |
796 KB |
02_connect_23.txt |
AC |
19 ms |
800 KB |
02_connect_24.txt |
AC |
19 ms |
800 KB |
02_connect_25.txt |
AC |
19 ms |
844 KB |
02_connect_26.txt |
AC |
17 ms |
800 KB |
02_connect_27.txt |
AC |
19 ms |
792 KB |
02_connect_28.txt |
AC |
31 ms |
924 KB |
02_connect_29.txt |
AC |
19 ms |
924 KB |