Submission #1064081


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dat{
  ll val,mx,idx[10];
  dat(){val=mx=0,memset(idx,0,sizeof(idx));}
};

vector<dat> T(1);
string str;
ll val;
ll dfs(int pos,int idx,ll sum){
  if(idx<0){
    T[pos].val+=val;
    return T[pos].mx+T[pos].val+sum;
  }
  
  int num=str[idx]-'0';
  if(!T[pos].idx[num])T[pos].idx[num]=T.size(),T.push_back(dat());
  ll res=dfs(T[pos].idx[num],idx-1,sum+T[pos].val);
  T[pos].mx=max(T[pos].mx,res-sum-T[pos].val);
  return res;
}

int main(){
  int n;
  cin>>n;
  while(n--){
    cin>>str>>val;
    dfs(0,str.size()-1,0);
    cout <<T[0].mx<<endl;
  }
  return 0;
}

Submission Info

Submission Time
Task E - 宝くじ
User haji
Language C++ (GCC 4.9.2)
Score 200
Code Size 674 Byte
Status AC
Exec Time 714 ms
Memory 50060 KB

Judge Result

Set Name All
Score / Max Score 200 / 200
Status
AC × 25
Set Name Test Cases
All scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt
Case Name Status Exec Time Memory
scrambled_00.txt AC 20 ms 916 KB
scrambled_01.txt AC 16 ms 796 KB
scrambled_02.txt AC 500 ms 800 KB
scrambled_03.txt AC 452 ms 928 KB
scrambled_04.txt AC 523 ms 792 KB
scrambled_05.txt AC 356 ms 920 KB
scrambled_06.txt AC 411 ms 916 KB
scrambled_07.txt AC 139 ms 800 KB
scrambled_08.txt AC 231 ms 932 KB
scrambled_09.txt AC 466 ms 796 KB
scrambled_10.txt AC 393 ms 736 KB
scrambled_11.txt AC 140 ms 800 KB
scrambled_12.txt AC 384 ms 924 KB
scrambled_13.txt AC 110 ms 924 KB
scrambled_14.txt AC 549 ms 25480 KB
scrambled_15.txt AC 45 ms 2408 KB
scrambled_16.txt AC 547 ms 25484 KB
scrambled_17.txt AC 103 ms 7048 KB
scrambled_18.txt AC 507 ms 25428 KB
scrambled_19.txt AC 714 ms 49988 KB
scrambled_20.txt AC 713 ms 49972 KB
scrambled_21.txt AC 480 ms 50060 KB
scrambled_22.txt AC 478 ms 50060 KB
scrambled_23.txt AC 117 ms 13192 KB
scrambled_24.txt AC 220 ms 25516 KB