結果

問題 No.3068 Speedrun (Hard)
ユーザー GOTKAKO
提出日時 2025-03-21 23:14:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,994 bytes
コンパイル時間 2,201 ms
コンパイル使用メモリ 203,800 KB
実行使用メモリ 14,768 KB
最終ジャッジ日時 2025-03-21 23:14:43
合計ジャッジ時間 5,846 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1
other AC * 6 WA * 1 RE * 1 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

long long extgcd(long long a, long long b, long long &x,long long &y){
    if(b == 0){x = 1,y = 0; return a;}
    long long g = extgcd(b,a%b,y,x);
    y -= a/b*x; return g;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,T,idx = 0;
    vector<tuple<int,int,int>> AB(4);
    for(auto &[a,b,p] : AB) cin >> a,p = idx++;
    cin >> N;
    for(auto &[a,b,p] : AB) cin >> b;
    sort(AB.begin(),AB.end(),[&](auto a,auto b){return get<1>(a) > get<1>(b);});
    cin >> T;

    auto [a1,b1,p1] = AB.at(0);
    auto [a2,b2,p2] = AB.at(1);
    auto [a3,b3,p3] = AB.at(2);
    auto [a4,b4,p4] = AB.at(3);
    auto output = [&](int i,int k,int l,int m) -> void {
        vector<int> answer(4);
        answer.at(p1) = i;
        answer.at(p2) = k;
        answer.at(p3) = l;
        answer.at(p4) = m;
        for(int i=0; i<4; i++) cout << answer.at(i) << (i==3?"\n":" ");
    };

    long long G = gcd(b3,b4),maxt = a3*b3+a4*b4;
    long long c3 = b4/G,c4 = b3/G;
    for(int i=0; i<=a1; i++){
        for(int k=0; k<=min(N-i,a2); k++){
            int n = N-i-k,t = T-i*b1-k*b2;
            if(t < 0) break;
            if(n == 0 && t == 0){
                output(i,k,0,0); return 0;
            }
            if(n == 0) break;
            if(t%G || t > maxt) continue;
            if(b3 == b4){
                long long three = min(t/G,0LL+b3),four = t/G-three;
                output(i,k,three,four); return 0;
            }
            
            long long l,m,g = extgcd(b3,b4,l,m);
            l *= t/G,m *= t/G;
            if((n-l-m)%(abs(c3-c4))) continue;
            long long change = (n-l-m)/(abs(c3-c4));
            if((change >= 0 && c3 > c4)||(change < 0 && c3 < c4)) l -= c3*change,m += c4*change; 
            else l += c3*change,m -= c4*change;

            if(0 <= l && l <= a3 && 0 <= m && m <= a4){
                output(i,k,l,m); return 0;
            }
        }
    }
    assert(false);
}
0