QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363515 | #7695. Double Up | pipoika# | TL | 1ms | 3800kb | C++20 | 4.5kb | 2024-03-23 23:39:12 | 2024-03-23 23:39:12 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,j,k) for (int i=j;i<(k);++i)
#define all(i) (i).begin(),(i).end()
#define sz(i) (int)(i).size()
using namespace std;
typedef vector<int> vi;
map<string,int> powmap = {{"1",0},
{"2",1},
{"4",2},
{"8",3},
{"16",4},
{"32",5},
{"64",6},
{"128",7},
{"256",8},
{"512",9},
{"1024",10},
{"2048",11},
{"4096",12},
{"8192",13},
{"16384",14},
{"32768",15},
{"65536",16},
{"131072",17},
{"262144",18},
{"524288",19},
{"1048576",20},
{"2097152",21},
{"4194304",22},
{"8388608",23},
{"16777216",24},
{"33554432",25},
{"67108864",26},
{"134217728",27},
{"268435456",28},
{"536870912",29},
{"1073741824",30},
{"2147483648",31},
{"4294967296",32},
{"8589934592",33},
{"17179869184",34},
{"34359738368",35},
{"68719476736",36},
{"137438953472",37},
{"274877906944",38},
{"549755813888",39},
{"1099511627776",40},
{"2199023255552",41},
{"4398046511104",42},
{"8796093022208",43},
{"17592186044416",44},
{"35184372088832",45},
{"70368744177664",46},
{"140737488355328",47},
{"281474976710656",48},
{"562949953421312",49},
{"1125899906842624",50},
{"2251799813685248",51},
{"4503599627370496",52},
{"9007199254740992",53},
{"18014398509481984",54},
{"36028797018963968",55},
{"72057594037927936",56},
{"144115188075855872",57},
{"288230376151711744",58},
{"576460752303423488",59},
{"1152921504606846976",60},
{"2305843009213693952",61},
{"4611686018427387904",62},
{"9223372036854775808",63},
{"18446744073709551616",64},
{"36893488147419103232",65},
{"73786976294838206464",66},
{"147573952589676412928",67},
{"295147905179352825856",68},
{"590295810358705651712",69},
{"1180591620717411303424",70},
{"2361183241434822606848",71},
{"4722366482869645213696",72},
{"9444732965739290427392",73},
{"18889465931478580854784",74},
{"37778931862957161709568",75},
{"75557863725914323419136",76},
{"151115727451828646838272",77},
{"302231454903657293676544",78},
{"604462909807314587353088",79},
{"1208925819614629174706176",80},
{"2417851639229258349412352",81},
{"4835703278458516698824704",82},
{"9671406556917033397649408",83},
{"19342813113834066795298816",84},
{"38685626227668133590597632",85},
{"77371252455336267181195264",86},
{"154742504910672534362390528",87},
{"309485009821345068724781056",88},
{"618970019642690137449562112",89},
{"1237940039285380274899124224",90},
{"2475880078570760549798248448",91},
{"4951760157141521099596496896",92},
{"9903520314283042199192993792",93},
{"19807040628566084398385987584",94},
{"39614081257132168796771975168",95},
{"79228162514264337593543950336",96},
{"158456325028528675187087900672",97},
{"316912650057057350374175801344",98},
{"633825300114114700748351602688",99},
{"1267650600228229401496703205376",100},
{"2535301200456458802993406410752",101},
{"5070602400912917605986812821504",102},
{"10141204801825835211973625643008",103},
{"20282409603651670423947251286016",104},
{"40564819207303340847894502572032",105},
{"81129638414606681695789005144064",106},
{"162259276829213363391578010288128",107},
{"324518553658426726783156020576256",108},
{"649037107316853453566312041152512",109},
{"1298074214633706907132624082305024",110},
{"2596148429267413814265248164610048",111},
{"5192296858534827628530496329220096",112},
{"10384593717069655257060992658440192",113},
{"20769187434139310514121985316880384",114},
{"41538374868278621028243970633760768",115},
{"83076749736557242056487941267521536",116},
{"166153499473114484112975882535043072",117},
{"332306998946228968225951765070086144",118},
{"664613997892457936451903530140172288",119},};
int rpow() {
string w;cin>>w;
assert(powmap.count(w));
return powmap[w];
}
vi nums;
unordered_map<int, int> memo;
int solve(int low, int high) {
if (low == high) return nums[low];
int key = (low << 10) | high;
if (memo.count(key)) return memo[key];
int ans = solve(low+1, high);
ans = max(ans, solve(low, high-1));
rep(split, low, high) {
int left = solve(low, split);
int right = solve(split+1, high);
int sub = max(left, right);
if (left == right) ++sub;
ans = max(ans, sub);
}
return memo[key] = ans;
}
int main() {
int n;
cin >> n;
nums.resize(n);
rep(i,0,n) nums[i] = rpow();
int ans = solve(0,n-1);
string output;
for (auto [k, v] : powmap) if (v == ans) {
// cout << k << ' ' << v << endl;
// output =
cout << k << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3800kb
input:
5 4 2 2 1 8
output:
16
result:
ok single line: '16'
Test #2:
score: -100
Time Limit Exceeded
input:
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...