結果

問題 No.2698 Many Asakatsu
ユーザー karinohito
提出日時 2024-03-16 05:25:19
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,343 bytes
コンパイル時間 10,781 ms
コンパイル使用メモリ 276,764 KB
最終ジャッジ日時 2025-02-20 06:44:14
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 WA * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'll f_i(int, ll)':
main.cpp:30:8: warning: 'p' may be used uninitialized [-Wmaybe-uninitialized]
   30 |     ll p;
      |        ^
main.cpp: In function 'int main()':
main.cpp:30:8: warning: 'p' may be used uninitialized [-Wmaybe-uninitialized]

ソースコード

diff # 

/*
O(Q*LP)
近傍を全探索
handmadeで落ちるはず
*/

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vll=vector<ll>;
using vvll=vector<vll>;


vll kousa,syoko;
int N,M,Q;
ll X;

//D[i][0]+D[i][1]+...+D[i][p-1]
ll SumD(ll i,ll p){
    if(p==0)return 0;
    return syoko[i]*p+p*(p-1)/2*kousa[i];
}

//f_i(x) O(1)
ll f_i(int i,ll x){
    ll p;
    if(x<=syoko[i])p=0;
    else if(x>syoko[i]+kousa[i]*(M-1))p=M;
    else if(kousa[i]!=0)p=(x-syoko[i]-1)/kousa[i]+1;
    ll res=(SumD(i,M)-SumD(i,p))-SumD(i,p)+p*x-(M-p)*x;
    return res;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>N>>M;
    
    kousa.resize(N);
    syoko.resize(N);
    for(int i=0;i<N;i++)cin>>syoko[i]>>kousa[i];

    cin>>Q>>X;
    vll C(N);
    for(int q=0;q<N;q++){
        cin>>C[q];
    }
    vector<ll> AN(Q);
    int L=0;
    int LP=300;
    for(int q=0;q<Q;q++){
        while(L<N-1){
            ll d=L;
            ll mi=1e18;
            for(ll i=L;i<min(N,L+LP);i++){
                ll fx=f_i(i,X);
                if(mi>fx)d=i,mi=fx;
            }
            if(L==d)break;
            L=d;
        }
        AN[q]=L+1;
        X+=C[L];
        
    }
    for(ll q=0;q<Q;q++)cout<<AN[q]<<" \n"[q==Q-1];
}
0