제출 #1332552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1332552		KALARRY	Trains (BOI24_trains)	C++20	100 / 100	390 ms	206748 KiB

Main

//chockolateman
 
#include<bits/stdc++.h>
 
using namespace std;
 
const int S = 100;
const long long MOD = 1e9 + 7;
 
long long N,d[100005],x[100005],dp[100005],cur_pos[S+5][S+5];
vector<pair<long long,long long>> sums[S+5][S+5]; 
 
int main()
{
    scanf("%lld",&N);
    for(int i = 1 ; i <= N ; i++)
        scanf("%lld%lld",&d[i],&x[i]);
    for(int i = 1 ; i <= N ; i++)
        for(int j = 1 ; j <= S ; j++)
            sums[j][i%j].push_back({0,0});
    for(int j = 1 ; j <= S ; j++)
        for(int i = 0 ; i < j ; i++)
            cur_pos[j][i] = -1;
    for(int i = N ; i >= 1 ; i--)
    {
        dp[i] = 1;
        if(d[i]!=0)
        {
            if(d[i] > S)
            {
                for(int j = i + d[i] ; j <= min(N,i + x[i]*d[i]) ; j+= d[i])
                {
                    dp[i] += dp[j];
                    dp[i] %= MOD;
                }
            }
            else
            {
                if(cur_pos[d[i]][i%d[i]] != -1)
                {
                    long long lim = min(N,i + x[i]*d[i]);
                    long long total_sum = sums[d[i]][i%d[i]][cur_pos[d[i]][i%d[i]]].second;
                    long long to_remove = 0;
                    if(sums[d[i]][i%d[i]][0].first > lim)
                    {
                        int pos = 0;
                        int prev_size = sums[d[i]][i%d[i]].size();
                        for(int b = prev_size-1 ; b >= 1 ; b/=2)
                            while(pos + b < prev_size && sums[d[i]][i%d[i]][pos+b].first > lim)
                                pos += b;
                        to_remove = sums[d[i]][i%d[i]][pos].second;
                    }
                    dp[i] += (total_sum - to_remove%MOD + MOD)%MOD;
                }
            }
        }
        for(int j = 1 ; j <= S ; j++)
        {
            if(cur_pos[j][i%j]==-1)
                sums[j][i%j][++cur_pos[j][i%j]] = {i,dp[i]};
            else
                sums[j][i%j][++cur_pos[j][i%j]] = {i,(dp[i] + sums[j][i%j][cur_pos[j][i%j]].second)%MOD};
        }
    }
    printf("%lld\n",dp[1]);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
Main.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%lld%lld",&d[i],&x[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29