C - Distribution Editorial by en_translator
First, the value \(\mathrm{memo}_i\) defined by the recurrence relations \(\mathrm{memo}_1=T_1, \mathrm{memo}_{i+1}=\mathrm{memo}_i+S_i\) expresses the time when the gem handed directly to the first Snuke arrives at \(i\)-th Snuke for the first time.
We can find out similarly what time do the gems given to the \(2, 3, \ldots,\) and \(N\)-th Snuke directly arrives at the \(i\)-th Snuke.
If we implement it naively, it can be solved in a total of \(O(N^2\)) time, but since it does not fit in the time limit, we have to make it faster.
Here, we can observe the fact that we can ignore the gems that a Snuke receives for the second time and later and put together the \(N\) calculations so far into one, to write a code like shown below.
Note that the loop has to be performed at least \(2N\) times.
Sample code (Python)
N = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
for i in range(N*2):
T[(i+1)%N] = min(T[(i+1)%N], T[i%N] + S[i%N])
for ans in T:
print(ans)
Sample code (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
vector<int> S(N), T(N);
for(int i = 0; i < N; i++) cin >> S[i];
for(int i = 0; i < N; i++) cin >> T[i];
vector<int> memo = T;
for(int i = 0; i < N*2; i++) memo[(i+1)%N] = min(memo[(i+1)%N], memo[i%N] + S[i%N]);
for(int ans: memo) cout << ans << endl;
}
posted:
last update: