結果

問題 No.2698 Many Asakatsu
ユーザー karinohitokarinohito
提出日時 2024-03-16 05:25:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,343 bytes
コンパイル時間 3,109 ms
コンパイル使用メモリ 221,480 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-09-30 03:52:01
合計ジャッジ時間 11,930 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 6 ms
6,816 KB
testcase_12 AC 7 ms
6,816 KB
testcase_13 AC 5 ms
6,816 KB
testcase_14 AC 6 ms
6,816 KB
testcase_15 AC 5 ms
6,820 KB
testcase_16 AC 6 ms
6,816 KB
testcase_17 AC 2 ms
6,820 KB
testcase_18 AC 7 ms
6,816 KB
testcase_19 AC 64 ms
6,816 KB
testcase_20 AC 55 ms
6,820 KB
testcase_21 AC 75 ms
6,820 KB
testcase_22 AC 269 ms
7,168 KB
testcase_23 AC 263 ms
7,168 KB
testcase_24 AC 261 ms
7,040 KB
testcase_25 AC 265 ms
7,296 KB
testcase_26 AC 263 ms
7,168 KB
testcase_27 AC 263 ms
7,040 KB
testcase_28 WA -
testcase_29 AC 261 ms
7,168 KB
testcase_30 AC 208 ms
7,040 KB
testcase_31 WA -
testcase_32 AC 1,140 ms
7,296 KB
testcase_33 AC 57 ms
6,820 KB
testcase_34 AC 1,065 ms
7,168 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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