結果

問題 No.3068 Speedrun (Hard)
ユーザー GOTKAKO
提出日時 2025-03-21 23:05:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,678 bytes
コンパイル時間 2,687 ms
コンパイル使用メモリ 199,524 KB
実行使用メモリ 14,776 KB
最終ジャッジ日時 2025-03-21 23:06:02
合計ジャッジ時間 19,790 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 WA * 2 TLE * 2 -- * 17
権限があれば一括ダウンロードができます

ソースコード

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;
    vector<pair<int,int>> AB(4);
    for(auto &[a,b] : AB) cin >> a;
    cin >> N;
    for(auto &[a,b] : AB) cin >> b;
    cin >> T;

    auto [a1,b1] = AB.at(0);
    auto [a2,b2] = AB.at(1);
    auto [a3,b3] = AB.at(2);
    auto [a4,b4] = AB.at(3);
    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){
                cout << i << " " << k << " 0 0" << endl; 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;
                cout << i << " " << k << " " << three << " " << four << endl; 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){
                cout << i << " " << k << " " << l << " " << m << endl; return 0;
            }
        }
    }
}
0