結果
| 問題 | No.3800 Screw manufacturing |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-14 00:14:36 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 66 ms / 2,000 ms |
| + 843µs | |
| コード長 | 2,298 bytes |
| 記録 | |
| コンパイル時間 | 1,800 ms |
| コンパイル使用メモリ | 244,784 KB |
| 実行使用メモリ | 19,220 KB |
| 最終ジャッジ日時 | 2026-11-14 00:14:44 |
| 合計ジャッジ時間 | 7,417 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 53 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
long long solve(vector<pair<long long,long long>> AB,long long T){
sort(AB.begin(),AB.end());
long long ret = 1e18;
do{
long long t1 = 0,t2 = 0;
for(auto [a,b] : AB){
if(t1) t1 += T,t2 += T;
t1 += a,t2 = max(t2,t1)+b;
}
ret = min(ret,t2);
}while(next_permutation(AB.begin(),AB.end()));
return ret;
}
random_device rnd;
mt19937 mt(rnd());
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
bool submit = true;
while(true){
long long N = mt()%3+3,T = mt()%10+1;
if(submit) cin >> N >> T;
vector<long long> R(N,1);
vector<tuple<long long,long long,long long>> big,small;
if(submit) for(auto &r : R) cin >> r;
for(int i=0; i<N; i++){
int a = mt()%5+1,b = mt()%5+1;
if(submit) cin >> a >> b;
if(a <= b) big.push_back({a,b,R.at(i)});
else small.push_back({b,a,R.at(i)});
}
sort(big.begin(),big.end());
sort(small.rbegin(),small.rend());
for(auto &[b,a,r] : small) swap(a,b);
long long t1 = 0,t2 = 0;
for(auto [a,b,r] : big){
if(t1) t1 += T;
if(t2) t2 += T;
t2 = max(t2,t1+a)+b*r,t1 += a*r;
t2 = max(t2,t1+b);
}
for(auto [a,b,r] : small){
if(t1) t1 += T;
if(t2) t2 += T;
t2 = max(t2,t1+a)+b*r,t1 += a*r;
t2 = max(t2,t1+b);
}
long long answer = t2;
if(submit == false){
vector<pair<long long,long long>> AB;
for(auto [a,b,r] : big) while(r--) AB.push_back({a,b});
for(auto [a,b,r] : small) while(r--) AB.push_back({a,b});
sort(AB.begin(),AB.end());
long long jury = solve(AB,T);
if(answer != jury){
cout << "Wrong" << endl;
cout << N << " " << T << endl;
for(auto [a,b,r] : big) cout << r << " ";
for(auto [a,b,r] : small) cout << r << " "; cout << endl;
for(auto [a,b,r] : big) cout << a << " " << b << endl;
for(auto [a,b,r] : small) cout << a << " " << b << endl;
cout << answer << " " << jury << endl; return 0;
}
}
cout << answer/(24*60) << " " << answer%(24*60)/60 << " " << answer%60 << endl;
if(submit) break;
}
}