Submission #00207

ソースコード

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a,b,c;
int wa[3010];
int sa_wa[3010];
pair<int,int> item[3010];
pair<int,int> event[1010];

// item power
vector<pair<int,int> >v[1010];

int ans[1010][3010];

int main(){
   
  // Input
  cin>>n>>m;
  wa[0] = 0;sa_wa[0] = 0;
  item[0].second = 0;
  for(int i=1;i<=n;i++){
    cin>>a>>b;
    wa[i] = wa[i-1] + a;
    item[i] = make_pair(a,b);
    c = item[i].second - item[i-1].second;
    if(c<0)c*=-1;
    sa_wa[i] = sa_wa[i-1]+c;
    if(i==1)sa_wa[i]=0;
  }
  for(int i=1;i<=m;i++){
    cin>>a>>b;
    event[i] = make_pair(a,b);
  }
  event[0] = make_pair(0,0);
   
  for(int i=0;i<=1000;i++)for(int j=0;j<=3000;j++)ans[i][j]=0;

  for(int i=1;i<=m;i++){
    for(int j=0;j<=n;j++){
       
      if(ans[i][j] < event[i-1].second)continue;
      if(ans[i][j] >= event[i].second){ ans[i+1][j] = max( ans[i+1][j],ans[i][j] ); continue; }
       
      int power = 0;
      int total;
      for(int k=j+1;k<=n;k++){        
        if( (event[i].first - wa[j]) < wa[k]-wa[j+1] )break;
        power += item[k].second;
        total = ans[i][j] + power + (sa_wa[k]-sa_wa[j+1]);
        if(total >= event[i].second){ ans[i+1][k] = max( ans[i+1][k],total );}
      }
    }
  }

  int Hina = -1;
  for(int i=n;i>=0;i--){
    cout<< ans[m+1][i]<<endl;
    if(ans[m+1][i] >= event[m].second)Hina = event[m].first - wa[i];
  }
   
  cout<< Hina << endl;

  return(0);
}

ステータス

項目	データ
問題	0010 - ゲームの攻略
ユーザー名	Eraim Unit
投稿日時	2017-09-06 18:38:46
言語	C++
状態	Wrong Answer
得点	0
ソースコード長	1446 Byte
最大実行時間	52 ms
最大メモリ使用量	12524 KB

セット

	セット	得点	Cases
1	ALL	0 / 20	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01.txt	WA	18 ms	12256 KB	1
in02.txt	WA	23 ms	12428 KB	1
in03.txt	WA	20 ms	12476 KB	1
in04.txt	WA	28 ms	12268 KB	1
in05.txt	WA	21 ms	12308 KB	1
in06.txt	WA	19 ms	12356 KB	1
in07.txt	WA	26 ms	12404 KB	1
in08.txt	WA	17 ms	12452 KB	1
in09.txt	WA	20 ms	12244 KB	1
in10.txt	WA	18 ms	12284 KB	1
in11.txt	WA	19 ms	12452 KB	1
in12.txt	WA	38 ms	12364 KB	1
in13.txt	WA	20 ms	12404 KB	1
in14.txt	WA	21 ms	12448 KB	1
in15.txt	WA	31 ms	12488 KB	1
in16.txt	WA	27 ms	12380 KB	1
in17.txt	WA	17 ms	12280 KB	1
in18.txt	WA	18 ms	12452 KB	1
in19.txt	WA	21 ms	12500 KB	1
in20.txt	WA	18 ms	12416 KB	1
in21.txt	WA	22 ms	12460 KB	1
in22.txt	WA	30 ms	12500 KB	1
in23.txt	WA	28 ms	12288 KB	1
in24.txt	WA	29 ms	12456 KB	1
in25.txt	WA	31 ms	12484 KB	1
in26.txt	WA	36 ms	12508 KB	1
in27.txt	WA	41 ms	12524 KB	1
in28.txt	WA	42 ms	12412 KB	1
in29.txt	WA	48 ms	12448 KB	1
in30.txt	WA	52 ms	12476 KB	1