Advertisement
YEZAELP

TOI17: Sequel

Jan 1st, 2022
1,022
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main(){
  6.  
  7.     int n, Q;
  8.     scanf("%d %d", &n, &Q);
  9.  
  10.     int ar[n + 1];
  11.     for(int i=1;i<=n;i++) scanf("%d", &ar[i]);
  12.  
  13.     int sqrtn = sqrt(n);
  14.     int dp[sqrtn + 1][n + 1];
  15.     for(int i=1;i<=sqrtn;i++){
  16.         for(int j=1;j<=n;j++){
  17.             dp[i][j] = dp[i][max(j - i, 0)] + ar[j];
  18.         }
  19.     }
  20.  
  21.     for(int q=1;q<=Q;q++){
  22.         int l, r, m;
  23.         scanf("%d %d %d", &l, &m, &r);
  24.         int ans = 0;
  25.         if(m < sqrtn)
  26.             ans = dp[m][l + m * ((r - l) / m)] - dp[m][l] + ar[l];
  27.         else{
  28.             for(int i=l;i<=r;i+=m) ans += ar[i];
  29.         }
  30.         printf("%d ", ans);
  31.     }
  32.  
  33.     return 0;
  34. }
Advertisement
RAW Paste Data Copied
Advertisement