# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
109237 |
2019-05-05T17:03:21 Z |
amiratou |
Miners (IOI07_miners) |
C++14 |
|
1500 ms |
85000 KB |
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)x.size()
#define ll long long
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int code(char car){
if(car=='M')return 0;
if(car=='F')return 1;
return 2;
}
int n,last1,last2;
string ph;
map<pair<pair<string,string>,int>,int> dp;
string change(string p,char car){
int idx;
if(sz(p)<3)idx=0;
else idx=1;
p+=car;
return p.substr(idx);
}
int solve(string mine1,string mine2,int idx){
if(idx==n)return 0;
if(dp.find({{mine1,mine2},idx})!=dp.end())
return dp[{{mine1,mine2},idx}];
string new1=change(mine1,ph[idx]);
set<char> myset;
for (int i = 0; i < sz(new1); ++i)
myset.insert(new1[i]);
int ans=sz(myset)+solve(new1,mine2,idx+1);
string new2=change(mine2,ph[idx]);
myset.clear();
for (int i = 0; i < sz(new2); ++i)
myset.insert(new2[i]);
ans=max(ans,sz(myset)+solve(mine1,new2,idx+1));
return dp[{{mine1,mine2},idx}]=ans;
}
int main(){
boost;
char car;
cin>>n>>ph;
cout<<solve("","",0);
return 0;
}
//long long
//array bounds
//special cases
//binary search
Compilation message
miners.cpp: In function 'int main()':
miners.cpp:55:7: warning: unused variable 'car' [-Wunused-variable]
char car;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
547 ms |
18680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1144 ms |
35556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1556 ms |
39700 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1549 ms |
48068 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1542 ms |
69976 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1563 ms |
85000 KB |
Time limit exceeded |