akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long 

int n,k; 
vector<int> arr(100005),dp(100005,-1);

int recur( int index)
{

    //base case
    if (index == n-1) return 0;

    // look up
    if (dp[index] != -1) return dp[index];

    //recursive case
    int mini=INT_MAX;
    for(int i=index+1;i<=min(index+k,n-1);i++){
        mini=min(mini,recur(i) + abs(arr[index] - arr[i]));
    }
   

    return dp[index]=mini;
}

signed main()
{
    // system("clear");
    fast 
    cin >> n>>k;

    for (int i = 0; i <n; i++) cin >> arr[i];

    cout << recur(0);

    return 0;

}

Measured memory_bytes: 9540
L = input()
N = len(L)
MOD = 10**9 + 7

dp = [[0 for _ in range(2)] for _ in range(N+1)]
dp[0][0] = 1


for i in range(N):
    if L[i] == "1":
        dp[i+1][1] += dp[i][1] * 3 # (a,b) = (0,0),(1,0),(0,1)
        dp[i+1][1] += dp[i][0] # (0,0)
        dp[i+1][0] += dp[i][0] * 2 # (1,0) (0,1)
    else:
        dp[i+1][1] += dp[i][1] * 3 # (a,b) = (0,0),(1,0),(0,1)
        # dp[i+1][1] += dp[i][0] # a + b = a xor b を満たせないので、この遷移はない
        dp[i+1][0] += dp[i][0]  # (0,0) 

    dp[i+1][1] %= MOD
    dp[i+1][0] %= MOD
    

print(sum(dp[-1]) % MOD)

Measured memory_bytes: 54432
#include<iostream>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  char a[n][m];
  int b[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>a[i][j];
      if(a[i][j]=='c'){
	b[i][j]=0;
      }
      else{
	b[i][j]=-1;
      }
    }
  }
  for(int i=0;i<n;i++){
    for(int j=1;j<m;j++){
      if(b[i][j]==-1){
      if(b[i][j-1]!=-1){
	    b[i][j]=b[i][j-1]+1;
	  }
	}
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cout<<b[i][j];
      if(j!=m-1){
	cout<<" ";
      }
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3092
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int N,K; cin>>N>>K;
	vector<int> h(N);
	int ans = 0;
	for(int i=0;i<N;i++){
		cin>>h.at(i);
		if(h.at(i)>=K){
			ans++;
		}
	}

	cout<<ans<<endl;
}


Measured memory_bytes: 640
//ABC156 B
#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

int main()
{
    long n;
    long k;
    cin>>n;
    cin>>k;
    long kk=1;
    if(n<=1){
        cout<<1;
        return 0;
    }
    for(int i=0;;i++){
        if(kk>n){
            cout<<i;
            return 0;
        }
        kk*=k;
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
#include <cmath>

int main() {
  size_t N;
  std::cin >> N;

  std::vector<double> x(N);
  std::vector<double> y(N);
  for (size_t i = 0; i < N; ++i) {
	std::cin >> x[i] >> y[i];
  }
  
  // すべての町間距離を計算する
  std::vector<double> distances(N * N);
  for (size_t i = 0; i < N; ++i) {
    for (size_t j = 0; j < N; ++j) {
      const double dx = x[i] - x[j];
      const double dy = y[i] - y[j];
      distances[i * N + j] = std::sqrt(dx * dx + dy * dy);
    }
  }

  // 距離の総和を計算する
  size_t n = 0;  // 順列の個数
  double result = 0.0;
  std::vector<size_t> indices(N);
  for (size_t i = 0; i < N; ++i) {
    indices[i] = i;
  }
  while (true) {
	for (size_t k = 1; k < N; ++k) {
      const auto i = indices[k - 1];
      const auto j = indices[k];
      result += distances[i * N + j];
    }
    n++;
    if (!std::next_permutation(indices.begin(), indices.end())) break;
  }

  // 結果発表
  std::cout << std::setprecision(20) << (result / double(n));
  return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X = INT()

years = [3, 5, 7]

if X in years:
	print("YES")
else:
	print("NO")


Measured memory_bytes: 5148
// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 2e5 + 5;

int n, X[N];
ll SEG[2][N << 2], Lazy;

#define md (s + e) >> 1
#define lc id << 1
#define rc lc ^ 1
void Update(bool b, int p, ll x, int id = 1, int s = 0, int e = n) {
	if (e - s < 2) { SEG[b][id] = x; return; }
	if (p < md) Update(b, p, x, lc, s, md);
	else Update(b, p, x, rc, md, e);
	SEG[b][id] = min(SEG[b][lc], SEG[b][rc]);
}
ll Get(bool b, int l, int r, int id = 1, int s = 0, int e = n) {
	if (l >= e || s >= r) return INF;
	if (l <= s && e <= r) return SEG[b][id];
	return min(Get(b, l, r, lc, s, md), Get(b, l, r, rc, md, e));
}
void Update(int p, ll x) {	Update(0, p, x - Lazy - p), Update(1, p, x - Lazy + p); }
ll DP(int i) { return Get(0, i, i + 1) + i + Lazy; }

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));
	
	memset(SEG, 63, sizeof SEG);
	int q, a, b; cin >> n >> q >> a >> b; a--, b--;
	X[0] = b;
	Update(a, 0);
	for (int i = 1; i <= q; i++) cin >> X[i], X[i]--;
	for (int i = 1; i <= q; i++) {
		ll dp = min(Get(0, 0, X[i]) + X[i], Get(1, X[i], n) - X[i]) + Lazy;
		Lazy += abs(X[i] - X[i - 1]);
		if (dp < DP(X[i - 1])) Update(X[i - 1], dp);
	}
	ll ans = INF;
	for (int i = 0; i < n; i++) ans = min(ans, DP(i));
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 13568
//#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cstring>
#include <cassert>

using namespace std;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(x...) cerr << __LINE__ << ": " << #x << " = "; DBG::_print(x)
#else
#define DEBUG(x...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

#define MAXN 200000
int F[MAXN+4];
int invF[MAXN+4];
void build_factorial_tables(int N, int MOD) {
   F[0] = 1;
   for (int i = 1; i <= N; ++i)
      F[i] = (F[i-1] * 1LL * i) % MOD;
   VI inv(N+1);
   inv[0]  = inv[1] = 1;
   invF[0] = invF[1] = 1;
   for (int i = 2; i <= N; ++i) {
      inv[i] = (MOD - (MOD / i) * 1LL * inv[MOD % i] % MOD) % MOD;
      invF[i] = (invF[i-1] * 1LL * inv[i]) % MOD;
   }
}

int nCk(int n, int k, int P) {
   if (n < 0 || k < 0 || k > n)  // invalid n or k
      return 0;
   long long res = F[n];
   res = (res * invF[k]) % P;
   res = (res * invF[n-k]) % P;
   return res;
}

const int MOD = 998244353;


llong powmod(llong x, llong n, unsigned int m) {
   if (n == 0) return 1 % m;
   return (n & 1) ?
      (powmod((x*x) % m, n/2, m) * x) % m :
       powmod((x*x) % m, n/2, m);
}


int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   int N, M, K;
   cin >> N >> M >> K;

   if (N == 1) {
      cout << M << '\n';
      return 0;
   }
   
   if (M == 1) {
      int res = K < N-1 ? 0 : 1;
      cout << res << '\n';
      return 0;
   }

   build_factorial_tables(N, MOD);

   llong res = 0;
   for (int k = 0; k <= K; ++k) {
      int split_points = N - 1 - k;
      llong nways_split = nCk(N-1, split_points, MOD);
      llong nways_color = (M * powmod(M-1, split_points, MOD)) % MOD;
   // DEBUG(k, M-1, split_points, nways_split, nways_color);
      res = (res + nways_split * nways_color) % MOD;
   }

   cout << res << '\n';

   return 0;
}


Measured memory_bytes: 5468
#include <bits/stdc++.h>
using namespace std;

int main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;

	if( A + B > C + D ){
		cout << "Left" << endl;
	}

	else if( A + B < C + D ){
		cout << "Right" << endl;
	}
	
	else{
		cout<< "Balanced"<< endl;
	}
}

Measured memory_bytes: 3592
#include <iostream>
#include <queue>
#include <vector>

using WNode = std::pair<uint32_t, uint32_t>;
using WGraph = std::vector<std::vector<WNode>>;
using rWNode = std::pair<uint32_t, uint32_t>;

int main() {
  uint32_t N = 0;
  std::cin >> N;
  WGraph G(N);
  for (size_t i = 0; i < N; i++) {
    uint32_t K = 0;
    std::cin >> i >> K;
    for (size_t j = 0; j < K; j++) {
      uint32_t node = 0, cost = 0;
      std::cin >> node >> cost;
      G[i].push_back({node, cost});
    }
  }

  const uint32_t start = 0;
  std::priority_queue<rWNode, std::vector<rWNode>, std::greater<rWNode>> Q;
  Q.push({0, start});
  std::vector<uint32_t> result(N, -1);
  std::vector<uint32_t> temp(N, -1);
  while (!Q.empty()) {
    uint32_t cost = Q.top().first, current = Q.top().second;
    Q.pop();

    if (result[current] <= cost) continue;
    result[current] = cost;

    for (auto &&g : G[current]) {
      if (result[g.first] != static_cast<uint32_t>(-1)) continue;
      if (temp[g.first] <= g.second + result[current]) continue;
      temp[g.first] = g.second + result[current];
      Q.push({g.second + result[current], g.first});
    }
  }

  for (size_t i = 0; i < N; i++) {
    std::cout << i << " " << result[i] << std::endl;
  }

  return 0;
}


Measured memory_bytes: 7836
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> grid(h);
    for(int i = 0; i < h; i++) cin >> grid[i];
    int ans = 0;
    for(int m1 = 0; m1 < (1 << h); m1++) {
        for(int m2 = 0; m2 < (1 << w); m2++) {
            int cnt = 0;
            for(int i = 0; i < h; i++) {
                for(int j = 0; j < w; j++) {
                    if((m1 & (1 << i)) && (m2 & (1 << j)) && grid[i][j] == '#') cnt += 1;
                }
            }
            if(cnt == k) ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3648
a = [int(_) for _ in input().split()]
if len(a) == 2 and 1 <= a[0] <= 16 and 1 <= a[1] <= 16 and a[0] + a[1] <= 16:
    if a[0] <= 8 and a[1] <= 8:
        print('Yay!')
    else:
        print(':(')
else:
    print('hoge!')

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <math.h>
#include <stdlib.h>
#include <numeric>

int main(){
	int a, b, c;
	std::cin >> a >> b >> c;
	std::cout << std::min(b/a, c) << std::endl;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int main(){
	int a,b,c;
	cin >> a >> b >> c;
	if(a==b)cout << c << endl;
	else if(c==b)cout << a << endl;
	else if(a==c)cout << b << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

const int Maxn = 505;

int n;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) {
            int b = 0;
            while (!((j - i) & 1 << b)) b++;
            b++;
            printf("%d%c", b, j + 1 <= n? ' ': '\n');
        }
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

int main(void)
{
    IOS
    int n, m;
    cin >> n >> m;
    vector<string> a(n),b(m);
    REP(i,n) cin >> a[i];
    REP(i,m) cin >> b[i];
    
    bool ans = false;
    REP(i,n-m+1) {
        REP(j,n-m+1) {
            bool tmp = true;
            REP(y,m) REP(x,m) {
                if (a[i+y][j+x] != b[y][x]) {
                    tmp = false;
                    break;
                }
            }
            if (tmp) {
                ans = true;
                break;
            }
        }
        if (ans) break;
    }

    ATYN(ans);

    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
	int n, mi = (int)1e9;
	scanf("%d", &n);
	int h[n];
	for(int i = 0 ; i < n ; i++){
		scanf("%d", h + i);
	}
	for(int i = n - 1 ; i >= 0 ; i--){
		mi = min(mi, h[i]);
		if(h[i] - mi > 1){
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    ll z = 0;
    int c = 0;
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'A') c++;
        else if (i + 1 < s.length() && s[i] == 'B' && s[i + 1] == 'C') z += c, i++;
        else c = 0;
    }
    cout << z;
}


Measured memory_bytes: 720
using System;

public class p1009
{
	p1009(){
		string str;
		string[] st;
		
		while((str=Console.ReadLine()) != null){
			st = str.Split(' ');
			Console.WriteLine("{0}", gcd(int.Parse(st[0]), int.Parse(st[1])));
		}
	}
	
	private int gcd(int a, int b){
		if(b == 0) return a;
		return gcd(b, a%b);
	}
	
	public static int Main(string[] args){
		new p1009();
		return 0;
	}
}

Measured memory_bytes: 5572
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);};};
const int MOD = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<62;

//xのn乗%modを計算
ll mod_pow(ll x,ll n,ll mod){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res*x%mod;
        x = x*x%mod;
        n >>= 1;
    }
    return res;
}

int main(void) {

    int n;
    cin>>n;
    int mod = 998244353;
    vll d(n);
    rep(i,n)cin>>d[i];
    ll maxd=0;
    for(int i=0;i<n;i++)maxd=max(maxd,d[i]);
    vll distance(maxd+1,0);
    for(int i=0;i<n;i++){
        distance[d[i]]++;
    }
    

    ll ans=1;
    if(d[0]!=0||distance[0]!=1){
        fin(0);
        return 0;
    }
    for(int i=1;i<maxd;i++){
        ans*=mod_pow(distance[i],distance[i+1],mod);
        ans%=mod;
    }
    fin(ans);
    // rep(i,distance.size()){
    //     cout<<distance[i]<<endl;
    // }


}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cstdlib>

using namespace std;

int main(){

	int a,b;
	cin >> a >> b;
	cout << max(max(a+b,a-b),max(a+b,a*b)) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<queue>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)

typedef long long int ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef pair<string,string> Pstring;
typedef pair<double,double> Pdouble;



int main() {
  ll n,m;

  cin >> n >> m;
  ll a1,a2;
  a1 = n*(n-1)/2;
  a2 = m*(m-1)/2;
  cout << a1+a2 << endl;
}

Measured memory_bytes: 256
import Data.List

main = interact $ unlines . map (show . entrance_examination) . read' . lines
 where
  read' ("0 0 0":_) = []
  read' (mnn:xs) = ((nmin,nmax), map read scores) : read' xs'
   where
    [m,nmin,nmax] = map read (words mnn)
    (scores,xs') = splitAt m xs

entrance_examination ((nmin,nmax),scores) = fst $ head $ filter ((==gapmax) . snd) $ map gap [nmax,nmax-1..nmin]
 where
  gap n = (n, scores!!(n-1) - scores!!n)
  gapmax = maximum $ map (snd . gap) [nmax,nmax-1..nmin]

Measured memory_bytes: 5472
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	if((n+m)%3==0 || n%3==0 || m%3==0)
	{
		printf("Possible\n");
	}
	else
	{
		printf("Impossible\n");
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
s = input()
ans = 0
for i in range(1000):
    tmp = str(i).zfill(3)
    number = [tmp[0],tmp[1],tmp[2],"OK"]
    pos = 0
    for ss in s:
        if ss == number[pos] and pos < 3:
            pos += 1
    if number[pos] == "OK":
        ans += 1
print(ans)

Measured memory_bytes: 73864
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)3e5 + 5;

ll fromLeft[MAXN], fromRight[MAXN];
int arr[MAXN];
int n;

void solve() {
  scanf("%d", &n);
  
  for (int i = 1; i <= 3 * n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  multiset<ll> S;
  ll bestSum = 0;
  
  for (int i = 1; i < n; ++i) {
    S.insert(arr[i]);
    bestSum += arr[i];
  }
  
  for (int i = n; i <= 2 * n; ++i) {
    fromLeft[i] = bestSum;
    bestSum += arr[i];
    S.insert(arr[i]);
    bestSum -= *S.begin();
    S.erase(S.begin());
  }
  
  S.clear();
  bestSum = 0;
  
  for (int i = 3 * n; i > 2 * n; --i) {
    S.insert(-arr[i]);
    bestSum -= arr[i];
  }
  
  for (int i = 2 * n; i >= n; --i) {
    fromRight[i] = bestSum;
    bestSum -= arr[i];
    S.insert(-arr[i]);
    bestSum -= *S.begin();
    S.erase(S.begin());
  }
  
  ll ans = (ll)-1e18;
  
  for (int i = n; i <= 2 * n; ++i) {
    ans = max(ans, arr[i] + fromLeft[i] + fromRight[i]);
  }
  
  printf("%lld\n", ans);
}

int main() {
  int tt = 1;
  
  while (tt--) {
    solve();
  }

  return 0;
}



Measured memory_bytes: 11184
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pii pair<int, int>
#define fr(n) for (int i = 0; i < n; i++)
#define fr1(n) for (int i = 1; i <= n; i++)
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    ll n, m, d;
    cin >> n >> m >> d;
    double a;
    if (!d) a = n;
    else a = (n - d) * 2;
    cout << setprecision(13) << (m - 1) * a / n / n;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;

int manage(int init,int year)
{
	int type; double rate; int cost;
	cin >> type >> rate >> cost;

	int m = init;
	int intere = 0;

	for ( int i=0; i<year; i++ )
	{
		if ( type==0 )
		{
			intere += int(m*rate);
			m -= cost;
			//cout << m << endl;
		}
		else
		{
			m += int(m*rate) - cost;
			//cout << m << endl;
		}
	}

	return m + intere;
}

int main()
{
	int m; cin>>m;

	for ( int test=0; test<m; test++ )
	{
		int init; cin>>init;
		int year; cin>>year;
		int n; cin>>n;

		int ans = 0;
		for ( int i=0; i<n; i++ )
			ans = max(ans,manage(init,year));
		cout << ans << endl;
	}
}

Measured memory_bytes: 0
#include <cstdio>
using namespace std;
int main(){
    int all, n;
    scanf("%d%d", &all, &n);
    int sum = 0;
    for(int i = 0; i < n; i ++){
        int a;
        scanf("%d", &a);
        sum += a;
    }
    if(sum >= all){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M, K;
	cin >> N >> M >> K;

	vector<int> A(N + 1), B(M);
	rep(i, 1, N + 1)
	{
		cin >> A[i];
		A[i] += A[i - 1];
	}
	rep(i, 0, M)
	{
		cin >> B[i];
		if (0 < i)B[i] += B[i - 1];
	}

	int ans = 0;
	rep(i, 0, N+1)
	{
		if (K < A[i])break;
		int res = i;
		int ind = upper_bound(all(B), K - A[i]) - B.begin();
		chmax(ans, res + ind);
	}

	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 6364
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        long B = sc.nextLong();
        long C = sc.nextLong();
        long D = sc.nextLong();

        long cGood = (B / C) - ((A - 1) / C);
        long dGood = (B / D) - ((A - 1) / D);
        long cdGood = (B / lcm(C, D)) - ((A - 1) / lcm(C, D));

        long bad = (B - A + 1) - (cGood + dGood - cdGood);
        System.out.println(bad);
    }

    private static long gcd(long x, long y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    private static long lcm(long x, long y) {
        return x * (y / gcd(x, y));
    }

}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
#include <iostream>
#include <math.h>    //pow(x,y)=x^y 99999とかの場合+1するif文
#include <algorithm> //sort(a.begin(), a.end());reverse(a.begin(), a.end());
#define rep(init, i, n) for (int i = init; i < (n); i++)
#define ll long long
#define rev(s) reverse(s.begin(), s.end())
#define sor(v) sort(v.begin(), v.end())
#define PI 3.14159265358979323846264338327950L
//コード自動整形 Shift + Option + F @vscode
using namespace std;

/////main/////
int main()
{
    ll n, b;
    ll modx = 1000000000 + 7;
    ll n9, n8;
    n8 = 8;
    //n9 = 9;
    cin >> n;

    vector<ll> a(n);
    b = 1;
    a.at(0) = 0;
    rep(0, i, n - 1)
    {

        //b = n9 - n8;
        //b %= modx;

        //a.at(i) %= modx;
        a.at(i + 1) = a.at(i) * 10 + 2 * b;
        b = 9*b+n8;
        n8 *= 8;
        //n9 *= 9;
        n8 %= modx;
        //n9 %= modx;
        
        b %= modx;
        a.at(i + 1) %= modx;
        //cout<<"b="<<b<<endl;
        //cout<<"n8="<<n8<<endl;
        //cout<<"n9="<<n9<<endl;
        //cout<<"a.at("<<i<<")="<<a.at(i)<<endl;
    }
    cout<<a.at(n-1)<<endl;
}
/////main/////

/////function/////

Measured memory_bytes: 11120
X = int(input())
if 400 <= X <=599:
    print(8)
elif 600 <= X <= 799:
    print(7)
elif 800 <= X <= 999:
    print(6)
elif 1000 <= X <= 1199:
    print(5)
elif 1200 <= X <= 1399:
    print(4)
elif 1400 <= X <= 1599:
    print(3)
elif 1600 <= X <= 1799:
    print(2)
elif 1800 <= X <= 1999:
    print(1)

Measured memory_bytes: 9184
/**********************************************************
* @Author: 			   Kirito
* @Last Modified by:   Kirito
* @Remark:
**********************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;

const int maxn=22;
int und[maxn],martix[maxn][maxn],ct[maxn];
int n,m,x;
int ans;

void dfs(int d,int cost){
    if(d>n){
        for(int i=0;i<m;i++){
            if(und[i]<x){
                return;
            }
        }
        ans=min(ans,cost);
        return;
    }
    int mid[maxn];
    for(int i=0;i<m;i++){
        mid[i]=und[i];
        und[i]+=martix[d][i];
    }
    dfs(d+1,cost+ct[d]);
    for(int i=0;i<m;i++){
        und[i]=mid[i];
    }
    dfs(d+1,cost);
    return;
}

int main()
{
    FAST;cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        cin>>ct[i];
        for(int j=0;j<m;j++){
            cin>>martix[i][j];
        }
    }
    CSE(und,0);ans=INF;
    dfs(1,0);
    if(ans==INF) cout<<"-1"<<endl;
    else cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3628
# coding:utf-8

import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


def main():
    n = II()
    pf = make_divisors(n)
    res = 0
    for x in pf[1:]:
        q, mod = divmod(n, x - 1)
        if q == mod:
            # print(x - 1)
            res += x - 1

    print(res)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
int x[101],a[10],b[10],c[10],u[101][101][10];

int dfs(int l, int r, int k) {
  if(u[l][r][k]!=-1) return u[l][r][k];
  if(l==r) return x[l]==a[k];
  int f=0;

  
  for(int i=l; i<r; i++) {
    f|=dfs(l,i,b[k])&dfs(i+1,r,c[k]);
  }
  u[l][r][k]=f;
  return f;
}

int main() {
  int n;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> x[i];
    for(int j=0; j<n; j++) {
      for(int k=0; k<10; k++) u[i][j][k]=-1;
    }
  }
  int m;
  cin >> m;
  for(int i=0; i<m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    b[i]--;
    c[i]--;
  }
  u[0][n-1][0]=dfs(0,n-1,0);
  if(u[0][n-1][0]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 1564
/**
  * @brief atcoder
  * @author yao
  */
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <climits>
#define ft first
#define sd second
#ifdef DBG
#   define dbg_pri(x...) fprintf(stderr,x)
#else
#   define dbg_pri(x...) 0
#   define NDEBUG
#endif //DBG
#include <cassert>

typedef unsigned int uint;
typedef long long int lli;
typedef unsigned long long int ulli;

#define N 524288
#define P 200003

constexpr ulli PRIME = 0xffffffff00000001;
constexpr ulli ntt_add(ulli a, ulli b)
{
    if(b>PRIME) b -= PRIME;
    ulli res = 0;
    bool f = __builtin_uaddll_overflow(a,b,&res);
    res -= -(ulli)f & PRIME;
    return res;
}
constexpr ulli ntt_sub(ulli a, ulli b)
{
    if(b>PRIME) b -= PRIME;
    ulli res = 0;
    bool f = __builtin_usubll_overflow(a,b,&res);
    res += -(ulli)f & PRIME;
    return res;
}
constexpr ulli ntt_mul(ulli a, ulli b)
{
    unsigned __int128 k = (unsigned __int128)a*b;
    ulli hh = k>>64>>32, hl = (uint)(k>>64), res = k;
    res = ntt_add(res,hl*-PRIME);
    res = ntt_sub(res,hh);
    return res;
}
constexpr ulli ntt_pow(ulli a, ulli b)
{
    ulli r = 1;
    while(b)
    {
        if(b&1) r = ntt_mul(r,a);
        a = ntt_mul(a,a);
        b >>= 1;
    }
    return r;
}
constexpr ulli ntt_find()
{
    ulli res = 2;
    while(ntt_pow(res,PRIME/2) != PRIME-1) ++res;
    return res;
}
constexpr ulli OMEGA = (ntt_pow(ntt_find(),PRIME/N));
static_assert(__builtin_popcount(N) == 1);
static_assert(PRIME%N == 1);
static_assert(ntt_pow(OMEGA,N/2) == PRIME-1);
uint ricr(uint k)
{
    k ^= (N-1);
    k ^= -1u >> 1 >> __builtin_clz(k);
    return k;
}
void ntt(ulli *a, ulli ow=OMEGA)
{
    for(int i=0,ii=0;i<N;++i,ii=ricr(ii))
        if(i<ii) std::swap(a[i],a[ii]);
    for(int n2=1,n=2;n2<N;n2=n,n*=2)
    {
        ulli w = ntt_pow(ow,N/n);
        for(ulli *p=a; p!=a+N; p+=n)
        {
            ulli k = 1;
            for(int i=0,j=n2;i<n2;++i,++j)
            {
                ulli e = p[i], o = p[j];
                ulli ok = ntt_mul(o,k);
                p[i] = ntt_add(e,ok);
                p[j] = ntt_sub(e,ok);
                k = ntt_mul(k,w);
            }
        }
    }
}
void ntt_inv(ulli *a)
{
    ntt(a,ntt_pow(OMEGA,PRIME-2));
    for(int i=0;i<N;++i) a[i] = ntt_mul(a[i],ntt_pow(N,PRIME-2));
}

int cnt[N];
ulli a[N];

int main()
{
    int n;
    lli ans = 0;
    scanf("%d", &n);
    for(int i=0;i<n;++i)
    {
        int k;
        scanf("%d", &k);
        ++cnt[k];
    }
    for(int i=0, k=1; i<P-1; ++i, k=k*2<P?k*2:k*2-P) a[i] = cnt[k];
    for(int i=0; i<P-1; ++i) cnt[i] = a[i];
    ntt(a);
    for(int i=0;i<N;++i) a[i] = ntt_mul(a[i],a[i]);
    ntt_inv(a);
    for(int i=0; i<P-1; ++i) a[i*2] = ntt_sub(a[i*2], cnt[i]);
    for(int i=0,k=1; i<N; ++i, k=k*2<P?k*2:k*2-P)
    {
        if(a[i] >= PRIME) a[i] -= PRIME;
        ans += k * a[i];
    }
    assert(ans%2==0);
    ans /= 2;
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 6608
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
#include<string>
#include<cstring>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
int gcd(int bunsi,int bunbo)
{
	if(bunbo==0)return bunsi;
	else gcd(bunbo,bunsi%bunbo);
}
int  main()
{
	string s;
	bool b;
	A:;
	while(cin>>s)
	{
		if(s=="#")return 0;
		int len=s.size();
		int bunbo=0;
		int bunsi=0;
		int cnt=count(s.begin(),s.end(),'w')+count(s.begin(),s.end(),'n');
		
	//	cnt=pow(2,cnt-1);
		b=true;
		if(cnt==1)
		{
			if(s=="west")cout<<90<<endl;
			else cout<<0<<endl;
			goto A;
		}
		{
			bunbo=pow(2,cnt-1);
			cnt--;
		}
		cnt=bunbo;
		//cnt--;
	//	cout<<"cnt: "<<cnt<<endl;
		for(int i=len-1;i>=0;i--)
		{
			
			if(s[i]=='w'&&b)
			{
				bunsi=90*(cnt);
				cnt/=2;
				b=false;
			}
			else if(s[i]=='n'&&b)
			{
				bunsi=0;
				cnt/=2;
				b=false;
			}
			else if(s[i]=='w'&&!b)
			{
				
				bunsi+=90*cnt;
				cnt/=2;
			}
			else if(s[i]=='n'&&!b)
			{
				
				bunsi-=90*cnt;
				cnt/=2;
			}
	//		cout<<"bunsi: "<<bunsi<<endl;
		}
		//bunbo*=2;
	//	cout<<"bunbo: "<<bunbo<<endl;
	int k=gcd(bunbo,bunsi);
//	cout<<"k: "<<k<<endl;
	//cout<<bunsi<<" "<<bunbo<<endl;
	if(bunsi%(bunbo)==0)cout<<bunsi/(bunbo)<<endl;
	else cout<<bunsi/k<<"/"<<bunbo/k<<endl;
	}
	return 0;
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define fo freopen("in.txt","r",stdin)
#define fc fclose(stdin)
#define fu0(i,n) for(i=0;i<n;i++)
#define fu1(i,n) for(i=1;i<=n;i++)
#define fd0(i,n) for(i=n-1;i>=0;i--)
#define fd1(i,n) for(i=n;i>0;i--)
#define mst(a,b) memset(a,b,sizeof(a))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define ss(s) scanf("%s",s)
#define sddd(n,m,k) scanf("%d %d %d",&n,&m,&k)
#define pans() printf("%d\n",ans)
#define all(a) a.begin(),a.end()
#define sc(c) scanf("%c",&c)
#define we(a) while(scanf("%d",&a)!=EOF)
const int maxn=200005;
const double eps=1e-8;
const int m=1e9+7;
bool a[maxn];
int C(int a,int b)
{
    if(a<b)
    {
        return 0;
    }
    else return a/b+C(a/b,b);
}
void init()
{
    memset(a,true,sizeof(a));
    a[0]=a[1]=false;
    for(int i=2;i<=maxn;i++)
    {
        if(a[i])
        {
            for(int j=i+i;j<maxn;j+=i)
            {
                a[j]=false;
            }
        }
    }
}
int main()
{
    int n;
    init();
    while(cin>>n)
    {
        ll sum=1;
        int i=2;
        while(i<=n)
        {
            if(a[i])
            {
                sum=sum*(ll)(C(n,i)+1)%m;
            }
            i++;
        }
        cout<<sum<<endl;
    }
    return 0;

}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define int long long
using namespace std;
using Graph = vector<vector<int>>;

signed main(){
  int N;
  cin >> N;
  
  vector<int> A(N+1);
  for( int i = 1; i <= N; i++ ) cin >> A.at(i);
  
  vector<int> B(N+1);
  vector<int> ans;
  for( int i = N; i > 0; i-- ){
    int sum = 0;
    for( int j = i*2; j <= N; j += i ){
      sum += B.at(j);
    }
    if( A.at(i) != sum%2 ){
      B.at(i)++;
      ans.push_back(i);
    }
  }
  
  cout << ans.size() << endl;
  for( int i = 0; i < ans.size(); i++ ) cout << ans.at(i) << " ";
  cout << endl;
}


Measured memory_bytes: 4980
// problem: "https://atcoder.jp/contests/abc156/tasks/abc156_b"

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n,k;
    cin>>n>>k;

    int c=0;

    while(n)
    {
        c++;
        n /= k;
    }

    cout<<c;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define min(x, y) (((x)<(y)) ? (x) : (y))

int main() {
	int i, j;
	int m, h, w, n;

	scanf("%d", &m);

	for (h = 1; h <= 3500; h++) {
		for (w = 1; w <=3500; w++) {
			if (4 * h*w <= m *(h+w)) continue;
			
			long long int x = (long long int)m * (long long int)(h*w);
			long long int y = (long long int)4*h*w - (long long int)(m*(h+w));
			
			long long int z = x / y;
			if (z * y == x ) {
				printf("%d %d %lld\n", h, w, z);
				return 0;
			}
		}
	}

	return 0;
}


Measured memory_bytes: 128
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    S, W = map(int, input().split())
    if S <= W:
        print("unsafe")
    else:
        print("safe")
        


if __name__ == '__main__':
    main()

Measured memory_bytes: 72748
n=int(input())
li=[input() for _ in range(n)]
ac=li.count("AC")
wa=li.count("WA")
tle=li.count("TLE")
re=li.count("RE")
print("AC x "+str(ac))
print("WA x "+str(wa))
print("TLE x "+str(tle))
print("RE x "+str(re))

Measured memory_bytes: 82752
n,a,b=map(int,input().split())
un=a+b
if n>un:
    res=n%un
    if res<=a:
        print((n//un)*a+res)
    else:
        print((n//un)*a+a)
else:
    if a>=n:
        print(n)
    else:
        print(a)

Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define pie 3.141592653589793238462643383279
#define INF 1000000007
#define ggr getchar(); getchar();return 0;
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}

int n, a[100010], ta;

signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	ta = a[0];
	rep(i, n)ta = gcd(ta, a[i]);
	cout << ta << endl;
	ggr
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <cmath>  
#include <cstdlib>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i <= n; i++) 

int main() {
    string s;
    cin >> s;
    if (s[0]==s[1] || s[1]==s[2] || s[2]==s[3]) {
        cout << "Bad" << endl;
    } else {
        cout << "Good" << endl;

    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    string s, t;
    cin >> s >> t;

    int maxt = 0;
    for (int i = 0; i < s.size() - t.size() + 1 ; i++) {
        int cnt = 0;
        for (int j = i; j <  i + t.size(); j++) {
            if (s[j] == t[j-i]) cnt++;
            maxt = max(cnt, maxt);
        }
    }

    cout << t.size() - maxt << endl;


    return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>
#include<string.h>
int main(void){
	int i=0,j=0;
	int x[4]={0,0,0,0};//NKXY

	for (j= 0; j< 4; ++j)
	{scanf("%d",&x[j]);//5 3 10000 9000
		}
	while(x[1]!=0){
			i+=x[2];
			x[1]--;
			x[0]--;
			if (x[0]==0)
			{
				printf("%d\n",i);
				return 0;
			}
	}
	i+=x[0]*x[3];
	printf("%d\n",i );

	return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<cmath>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<numeric>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main()
{
    int N;
    cin >> N;
    int c[N],s[N],f[N];
    for (int i=0; i<N-1; ++i)
    {
        cin >> c[i] >> s[i] >> f[i];
    }

    int ans[N];
    for (int i=0; i<N-1; ++i)
    {
        int t = 0;
        t += c[i] + s[i];
        for (int j=i+1; j<N-1; ++j)
        {
            if (t<=s[j]) t = s[j];//このパターンなし
            else
            {
                int sub = t - s[j];//始発後の経過時間
                if(sub % f[j] != 0)//待ち時間発生
                {
                    t = s[j] + ((int)sub/f[j] + 1)*f[j];
                }
            }
            t += c[j];
        }
        ans[i] = t;
    }
    ans[N-1] = 0;

    for (int i=0; i<N; ++i)
    {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import numpy as np
import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        S = [0 if c == '#' else 1 for c in input().strip()]
        A.append(S)

    A = np.array(A)
    up = np.zeros((H+1, W), dtype=np.int)
    down = np.zeros((H+1, W), dtype=np.int)
    right = np.zeros((H, W+1), dtype=np.int)
    left = np.zeros((H, W+1), dtype=np.int)

    for i in range(1, H+1):
        up[i] = (up[i-1] + 1) * A[i-1]
        down[H-i] = (down[H-i+1] + 1) * A[H-i]

    for i in range(1, W+1):
        right[:, i] = (right[:, i-1] + 1) * A[:, i-1]
        left[:, W-i] = (left[:, W-i+1] + 1) * A[:, W-i]

    R = (up[1:] + down[:H] - 1) * A
    C = (right[:, 1:] + left[:, :W] - 1) * A
    W = (R + C - 1) * A
    return W.max()


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 325948
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int n, m, M;
  int d[8];
  char c;
  scanf("%d\n", &n);
  for (int i=0; i<n; i++) {
    for(int j=0; j<8; j++) {
      scanf("%c", &c);
      d[j] = c - '0';
    }
    getchar();
    sort(d, d+8);
    m = 0;
    M = 0;
    for (int j=0; j<8; j++) {
      m *= 10;
      M *= 10;
      m += d[j];
      M += d[7-j];
    }
    printf("%d\n", M-m);
  }
  return 0;
}

Measured memory_bytes: 1044
#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<bitset>
#define int long long
#define hh putchar('\n')
#define kg putchar(' ')
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxn=300005,mod=998244353;
int n,m,aa[maxn],vis[maxn],q[maxn],tot,pos,ren[maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
		if(ch=='-')
			f=-1;
		ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
    }
    return x*f;
}
inline void write(int a)
{
    if(a<0)
    {
		putchar('-');
		putchar('1');
    }
    else
    {
		if(a>=10)
			write(a/10);
		putchar(a%10+'0');
    }
}
int calc(int xx,int yy)
{
	return n*(xx-1)+yy-1;
}
int fo()
{
	int kotae=1;
	for(int i=1;i<=18;++i)
		kotae*=10;
	return kotae;
}
signed main()
{	
	n=read(),m=1;
	for(int i=1;i<=n;++i)
	{
		aa[i]=read();
		if(!aa[i])
		{
			cout<<0<<endl;
			return 0;
		}
	}
	for(int i=1;i<=n;++i)
	{
		int a=aa[i];
		if(a&&1.0*1e18/a<m)
		{
			cout<<-1<<endl;
			return 0;
		}
		m*=a;
		if(m>fo())
		{
			cout<<-1<<endl;
			return 0;
		}
	}
	cout<<m<<endl;
    return 0;
}


Measured memory_bytes: 4384
#include <bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = INT_MAX / 2;

int main() {
  int N; cin >> N;
  vector<pair<int, int>> vs;
  rep(i, N) {
    int X, L; cin >> X >> L;
    vs.emplace_back(X - L, X + L);
  }
  sort(vs.begin(), vs.end(), [](auto &x, auto &y){ return x.second < y.second; });
  int curr = 0;
  int next = 1;
  int count = 0;
  while (1) {
    if (next == vs.size()) {
      break;
    }
    if (vs[next].first < vs[curr].second) {
      count++;
    }
    else {
      curr = next;
    }
    next++;
  }
  cout << N - count << endl;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

int main() {
    ll n, k; cin >> n >> k;
    vector<ll> t(n), d(n);
    vector<vector<ll>> sushi(n);
    for(int i = 0; i < n; ++i) {
        cin >> t[i] >> d[i];
        t[i]--;
        sushi[t[i]].push_back(d[i]);
    }
    vector<pll> v;
    for(int i = 0; i < n; ++i) {
        sort(rbegin(sushi[i]), rend(sushi[i]));
        if(!sushi[i].empty()) {
            v.emplace_back(sushi[i][0], i);
        }
    }
    sort(rbegin(v), rend(v));

    priority_queue<ll, vector<ll>, greater<>> que;
    int sz = 0;
    ll ans = 0, tans = 0;
    for(ll x = 0; x < min(k, (ll)v.size()); ++x) {
        const int id = v[x].second;
        tans += sushi[id][0];
        sz += 1;
        if(sz > k) {
            tans -= que.top();
            que.pop();
            sz--;
        }
        for(int j = 1; j < (int)sushi[id].size(); ++j) {
            if(sz < k) {
                tans += sushi[id][j];
                que.push(sushi[id][j]);
                sz += 1;
            } else if(sz == k && !que.empty() && que.top() < sushi[id][j]) {
                tans += sushi[id][j] - que.top();
                que.pop();
                que.push(sushi[id][j]);
            }
        }
        ans = max(ans, tans + (x + 1) * (x + 1));
    }

    cout << ans << endl;
}


Measured memory_bytes: 9460
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  vector<int> ABC(3);
  REP(i, 3){
    cin >> ABC[i];
  }
  int K; cin >> K;
  int ans = 0;
  REP(i, 3){
    int res =  ABC[i];
    REP(j, K){
      res *= 2;
    }
    res += ABC[(i+1)%3] + ABC[(i+2)%3];
    ans = max(ans, res);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3636
import sys, random, math
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

def main():
    inf = 10 ** 20

#    t = int(input())
#    t, a, b = map(int, input().split())
    t = 1
    
    for _ in range(1, t+1):
    #    print("Case #{}: ".format(_), end = '')
        
        n = int(input())
        a = [int(x) for x in input().split()]
        
        ans = 0
        node = 1
        sua = sum(a)
        for x in a:
            ans += node
            if(x > node):
                ans = -1
                break
            node -= x
            sua -= x
            node = min(node*2, sua)
        
        
        print(ans)
        
        
main()

Measured memory_bytes: 93240
#include<bits/stdc++.h>
using namespace std;
 
typedef vector <int> vi;
typedef pair< int ,int > pii;
#define endl "\n"
#define sd(val) scanf("%d",&val)
#define ss(val) scanf("%s",&val)
#define sl(val) scanf("%lld",&val)
#define debug(val) printf("check%d\n",val)
#define all(v) v.begin(),v.end()
#define PB push_back
#define MP make_pair
#define FF first
#define SS second
#define ll long long
#define MOD 1000000007
#define clr(val) memset(val,0,sizeof(val))
#define what_is(x) cerr << #x << " is " << x << endl;
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
 
int main()
{
 int t; cin >> t;
 cout << (ceil(t/1000.00) * 1000)-t ;
 
 
return 0;
   
}

Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n,a,b;
    cin>>n>>a>>b;
    if(n>1&&b>=a||n==1&&a==b)
        cout<<(n-2)*(b-a)+1;
    else
        cout<<0;
    return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <numeric>//accumulate(v.begin(), v.end(), 0);
#include <algorithm>//sort(v.begin(),v.end());
#include <string>//
#include <cmath>
#include <iomanip> //setprecision(2)
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main(){
        string s;
        int N;
        cin >> s;
        N=s.size();
        ll ans = 0;
        rep(i,1 << (N - 1)) {
                ll sm = 0;
                ll a = s[0] - '0';
                rep(j,N-1) {
                        if (i & (1 << j)) {
                                sm += a;
                                a = 0;
                        }
                        a = a * 10 + s[j + 1] - '0';
                }
                sm += a;
                ans += sm;
        }
        cout << ans << endl;

        return 0;
}


Measured memory_bytes: 256