QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363515#7695. Double Uppipoika#TL 1ms3800kbC++204.5kb2024-03-23 23:39:122024-03-23 23:39:12

Judging History

你现在查看的是最新测评结果

  • [2024-03-23 23:39:12]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3800kb
  • [2024-03-23 23:39:12]
  • 提交

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...

output:


result: