結果
問題 | No.1029 JJOOII 3 |
ユーザー |
|
提出日時 | 2020-04-22 03:45:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 684 bytes |
コンパイル時間 | 861 ms |
コンパイル使用メモリ | 69,852 KB |
実行使用メモリ | 6,016 KB |
最終ジャッジ日時 | 2024-10-10 01:05:21 |
合計ジャッジ時間 | 3,814 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
コンパイルメッセージ
main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 9 | main() | ^~~~
ソースコード
#include<iostream> #include<algorithm> using namespace std; int N,K; string s[80]; int C[80]; long dp[3<<17]; int cnt[3][80]; main() { cin>>N>>K; for(int i=0;i<N;i++) { cin>>s[i]>>C[i]; for(char c:s[i]) { cnt[c=='J'?0:c=='O'?1:2][i]++; } } for(int i=0;i<=3*K;i++)dp[i]=4e18; dp[0]=0; for(int i=0;i<3*K;i++) { for(int j=0;j<N;j++) { int nxt=i+cnt[i/K][j]; if(i/K==nxt/K) { dp[nxt]=min(dp[nxt],dp[i]+C[j]); continue; } nxt=i; for(char c:s[j]) { char dir=nxt/K==0?'J':nxt/K==1?'O':'I'; if(dir==c)nxt++; if(nxt==3*K)break; } dp[nxt]=min(dp[nxt],dp[i]+C[j]); } } long ans=dp[3*K]; cout<<(ans<3e18?ans:-1)<<endl; }