akhauriyash/Code-Regression huggingface dataset:
#ifndef COMPETITIVE_HEADER
    #pragma GCC optimize ("Ofast")
    #ifdef ONLINE_JUDGE
        #pragma GCC target ("avx512f")
    #else
        #pragma GCC target ("avx")
    #endif
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;
#endif


int n,q,ai,bi,ci;
map<int,int> am;
int ret;

signed main(){
    I(n);
    REP(i,n){
        I(ai);
        am[ai]++;
    }
    for(auto p: am) ret += p.first * p.second;
    I(q);
    REP(i,q){
        I(bi); I(ci);
        auto nmv = am[bi];
        ret += (ci- bi) * nmv;
        am[bi] = 0;
        am[ci] += nmv;
        printf("%lld\n", ret);
    }
}

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

int main(void) {
	int n; cin >> n;
	string s; cin >> s;

	int ans = 0;
	rep(i, n-2) {
		if (s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C') {
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

//入力したマスbが、-1にたどり着くなら-1, nにたどり着くなら1を返す
int simulate(char *s, char *t, char *d, int n, int q, int b){
    int i;
    for(i = 0; i < q; ++i) {
        if(s[b] == t[i]) {
            b += ((d[i] == 'R') ? 1 : -1);
            if(b < 0)   { return -1; }
            if(b > n-1) { return  1; }
        }
    }
    return 0;
}

int main()
{
    int n, q, i, a, b, b_prev, c, l, r;
    char s[200000], t[200000], d[200000];
    scanf("%d %d", &n, &q);
    scanf("%s", s);
    for(i = 0; i < q; ++i) {
        scanf("\n %c %c", &t[i], &d[i]);
    }

    //二部探索
    //aには「-1にたどり着くマスの中で最も右にあるもの」が最終的に入る
    a = 0; b_prev = -1; c = n-1;
    while(1) {
        b = (a + c + 1)/2;
        //printf("a:%d b:%d c:%d\n", a, b, c);
        if(b == b_prev) { break; }
        if(simulate(s, t, d, n, q, b) < 0) { a = b; }
        else { c = b; }
        b_prev = b;
        //printf("a:%d c:%d\n", a, c);
    }
    l = a;
    //printf("\n");

    //二部探索
    //aには「nにたどり着かないマスの中で最も右にあるもの」が最終的に入る
    a = 0; b_prev = -1; c = n-1;
    while(1) {
        b = (a + c + 1)/2;
        //printf("a:%d b:%d c:%d\n", a, b, c);
        if(b == b_prev) { break; }
        if(simulate(s, t, d,n, q, b) > 0) { c = b; }
        else { a = b; }
        b_prev = b;
        //printf("a:%d c:%d\n", a, c);
    }
    r = a;
    //printf("\n");
    //printf("r: %d l: %d\n", r, l);
    printf("%d\n", r - l);
    return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;

using i64 = long long;

i64 solve(i64 x,i64 y) {
	if (x <= y) {
		i64 ans = y - x;
		ans = min(ans, abs(y + x) + 1);
		return ans;
	}
	else {
		if (y <= 0 && 0 <= x) {
			return abs(-x - y) + 1;
		}
		if (y >= 0 && x >= 0) {
			return solve(-x, y) + 1;
		}
		if (y <= 0 && x <= 0) {
			return solve(x, -y) + 1;
		}
	}
}

int main() {
	i64 x, y;
	cin >> x >> y;
	cout << solve(x, y) << endl;
	return 0;
}

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

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct Edge{int from, to; ll cost;};

const ll MOD = 1000000007;
const long double EPS = 10e-10;

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int a,b;
    cin >> a >> b;
    if(a < b) swap(a, b);
    cout << ((16 - 2*b)/2 >= (a-b) ? "Yay!" : ":(") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i <= N; i++)
#define ll long long int
using namespace std;

int main(){
ll N, M;cin >> N >> M;
vector<ll> div;

rep(i, 1, sqrtl(M)){
    
    if(M%i == 0){
        
        div.push_back(i);div.push_back(M/i);

    }

}

sort(ALL(div));//for(auto v : div)cout << v << " ";

ll a, L = div.size();

rep(i, 0, L - 1){

    if(N <= div[i]){a = div[i];break;}

}

cout << M/a;

}

Measured memory_bytes: 3688
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#define _USE_MATH_DEFINES
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775808;

int main() {
    int N, P;
    cin >> N >> P;
    int a[N];
    ll even = 0;
    ll odd = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        if (a[i] % 2 == 0) {
            even++;
        } else {
            odd++;
        }
    }
    ll ans = 0;
    ll osel = 0;
    ll n = 1;
    ll esel = n << even;
    if (P == 0) {
        osel = 1;
        for (int i = 2; i <= odd; i += 2) {
            ll num = 1;
            for (int j = 1; j <= i; j++) {
                num = num * (odd - j + 1) / j;
            }
            osel += num;
        }
    } else {
        for (int i = 1; i <= odd; i += 2) {
            ll num = 1;
            for (int j = 1; j <= i; j++) {
                num = num * (odd - j + 1) / j;
            }
            osel += num;
        }
    }
    ans = osel * esel;
    cout << ans << endl;
}


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def bit_pattern(bits, length):
    return [(bits >> i) & 1 for i in range(length)]

def main():
    H, W, K = LI()
    s = SR(H)

    ans = float("inf")

    for i in range(1 << (H - 1)):
        pattern = bit_pattern(i, H-1)
        divided = []
        tmp = [s[0]]
        tmp_ans = 0

        for i, bit in enumerate(pattern):
            if bit:
                tmp_ans += 1
                divided.append(tmp)
                tmp = [s[i+1]]
            else:
                tmp.append(s[i+1])
        divided.append(tmp)

        whites = []

        for block in divided:
            white = [0] * W
            for row in block:
                for i, panel in enumerate(row):
                    if panel == "1":
                        white[i] += 1
            whites.append(white)

        curs = [0] * len(whites)
        outer = False
        for w in range(W):
            for i, white in enumerate(whites):
                if white[w] > K:
                    outer = True
                    break
                elif white[w] + curs[i] > K:
                    curs = [white[w] for white in whites]
                    tmp_ans += 1
                    break
                else:
                    curs[i] += white[w]
            else:
                continue
            if outer:
                break
        else:
            ans = min(ans, tmp_ans)

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 80080
#include<iostream>
#include<string>
#include<cmath>
//#include<array>
#include<algorithm>
#include<deque>
#include<vector>
//#include<utility>
//#include<set>
#include<map>
//#include<list>

using namespace std;
using LLI = long long int;
LLI N;

//vector<int>dir_x = { 0,0,1,1,1,-1,-1,-1 };
//vector<int>dir_y = { 1,-1,1,0,-1,1,0,-1 };
//vector<int>dir_x2 = { 0,0,1,-1 };
//vector<int>dir_y2 = { 1,-1,0,0 };
//vector<char>alp = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };

//class UnionFind {
//public:
//	vector<int>data;
//	UnionFind(int size) :data(size, -1) {};
//	bool unionset(int x, int y) {
//		x = root(x), y = root(y);
//		if (x != y) {
//			if (data[y] < data[x]) {
//				swap(x, y);
//			}
//			data[x] += data[y];
//			data[y] = x;
//		}
//		return x != y;
//	}
//	bool findset(int x, int y) {
//		return root(x) == root(y);
//	}
//	int root(int x) {
//		return data[x] < 0 ? x : data[x] = root(data[x]);
//	}
//	int size(int x) {
//		return -data[root(x)];
//	}
//};

//LLI gcd(LLI x, LLI y) {
//	LLI tmp, r;
//	if (x < y) {
//		tmp = x;
//		x = y;
//		y = tmp;
//	}
//	r = x % y;
//	while (r != 0) {
//		x = y;
//		y = r;
//		r = x % y;
//	}
//	return y;
//}
//LLI lcm(LLI x,LLI y) {
//	return x / gcd(x,y) * y;
//}

//long nCr(int n,int r) {
//	long ans = 1;
//	for (int i = n; i > n - r;i--) {
//		ans = ans * i;
//	}
//	for (int i = 1; i < r + 1;i++) {
//		ans = ans / i;
//	}
//	return ans;
//}

//const int n_max = 8;
//array<array<bool, n_max>, n_max>graph;
//int dfs(int v,int N,array<bool,n_max>visited) {
//	int ret = 0;
//	bool all_visited = true;
//	for (int i = 0; i < N;i++) {
//		if (visited[i] == false) {
//			all_visited = false;
//		}
//	}	
//	if (all_visited) {
//		return 1;
//	}
//	for (int i = 0; i < N;i++) {
//		if (graph[v][i] == false) {
//			continue;
//		}
//		if (visited[i] == true) {
//			continue;
//		}
//		visited[i] = true;
//		ret += dfs(i,N,visited);
//		visited[i] = false;
//	}
//	return ret;
//}

//vector<vector<int>>sub;
//int dfs(int id) {
//	if (sub[id].size() == 0) {
//		return 1;
//	}
//	int minP = (int)1e9;
//	int maxP = 0;
//	for (int i : sub[id]) {
//		int P = dfs(i);
//		minP = min(minP, P);
//		maxP = max(maxP, P);
//	}
//	return minP + maxP + 1;
//}

int main(void) {
	vector<int>vec;
	int a,MIN = 10,res = 0;
	bool c = false,d = true;
	for (int i = 0; i < 5;i++) {
		cin >> a;
		vec.push_back(a);
	}
	for (int i = 0; i < 5;i++) {
		if (vec[i] % 10 != 0) {
			res += 10;
		}
		if (vec[i] % 10 == 0) {

		}
		else if (vec[i]%10 < MIN) {
			MIN = vec[i] % 10;
			c = true;
		}
	}
	for (int i = 0; i < 5; i++) {
			vec[i] /= 10;
			vec[i] *= 10;
	}
	for (int i = 0; i < 5; i++) {
		res += vec[i];
	}
	if (c) {
		res += MIN;
	}
	if (c == false) {
		res += 10;
	}
		res -= 10;
	
	cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
    // Your code here!
    string x, y;
    cin >> x >> y;
    if(x == y){
        cout << "=" << endl;
    } else if (x > y) {
        cout << ">" << endl;
    } else {
        cout << "<" << endl;
    }
}


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

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N; cin >> N;
    ll X, M; cin >> X >> M;
    vector<pair<int, int>> appear(M, pair<int, int>(-1, -1));
    appear[X].first = 0;
    bool become_zero = false;
    ll now = X;
    ll ans = 0;
    ll reappear_num = -1;
    rep(i, M){
        now = (now * now) % M;
        if(now == 0){
            become_zero = true;
            break;
        }
        else if(appear[now].first != -1){
            reappear_num = now;
            appear[now].second = i+1;
            break;
        }
        else appear[now].first = i+1;
    }
    if(become_zero){
        now = X;
        rep(i, N){
            if(now == 0) break;
            ans += now;
            now = (now * now) % M;
        }
    }
    else{
        ll orbit_len = appear[reappear_num].second - appear[reappear_num].first;
        ll beg = appear[reappear_num].first;
        ll whole = ((N-beg) - ((N-beg) % orbit_len)) / orbit_len, las = N - beg - whole*orbit_len;
        ll now = reappear_num;
        rep(i, orbit_len) {ans += now; now = (now*now) % M;}
        
        //cout << whole << " " << beg << " " << las << endl;

        ans *= whole;
        now = X;
        rep(i, beg){
            ans += now;
            now = (now * now) % M;
        }
        now = reappear_num;
        rep(i, las){
            ans += now;
            now = (now * now) % M;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3996
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

m = I()
print(48 - m)

Measured memory_bytes: 65368
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define set_bits(a) __builtin_popcount(a)
#define pb push_back
#define pf push_front
#define mod 1000000007
#define M 998244353
#define fi first
#define se second
#define endl '\n'
#define INF 1e18
#define PI 3.14159265358979323846
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


int main()
{
    ll n,k,i;
    cin>>n>>k;
    ll arr[n];
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    ll ans=0;
    for(i=0;i<k;i++)
    {
        ans+=arr[i];
    }
    cout<<ans;
}


Measured memory_bytes: 3628
K = int(input())

queue = [i for i in range(1, 10)]

for i in range(K - 1):
    N = queue.pop(0)
    if i < K // 2.5:
        if N % 10 == 0:
            queue.append(N * 10)
            queue.append(N * 10 + 1)
        elif N % 10 == 9:
            queue.append(N * 10 + 8)
            queue.append(N * 10 + 9)
        else:
            queue.append(N * 10 + (N % 10 - 1))
            queue.append(N * 10 + N % 10)
            queue.append(N * 10 + (N % 10 + 1))

print(queue.pop(0))

Measured memory_bytes: 6916
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int prime[110];
int ans;
int N;

void check(int a, int b, int c) {
    a--; b--; c--;
    REP(i, 2, N) {
        REP(j, 2, N) {
            bool f = false;
            REP(k, 2, N) {
                if (i == j || j == k || k == i) continue;
                if (a == b && i > j) continue;
                if (prime[i] >= a && prime[j] >= b && prime[k] >= c) {
                    ans++;
                    f = true;
                }
                if (c == 0) break;
            }
            if (b == 0 && f) break;
        }
    }
}



int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    REP(i, 1, N) {
        int tmp = i;
        int j = 2;
        while(tmp > 1) {
            while(tmp % j == 0) {
                prime[j]++;
                tmp /= j;
            }
            j++;
        }
    }
    check(75, 1, 1);
    check(25, 3, 1);
    check(15, 5, 1);
    check(5, 5, 3);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
MOD = 998244353

LR = []

for i in range(K):
    l, r = map(int, input().split())
    LR.append([l, r])

dp = [0] * (N + 1)
dp[1] = 1
cumsum = [0, 1]

for i in range(2, N + 1):
    for l, r in LR:
        if i - l >= 1:
            dp[i] += (cumsum[i - l] - cumsum[max(i - r - 1, 0)]) % MOD
    dp[i] = dp[i] % MOD
    cumsum.append(cumsum[-1] + dp[i])

print(dp[-1] % MOD)


Measured memory_bytes: 81076
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <cmath>
#include <iomanip>
#include <stdexcept>
// #include <bits/stdc++.h>
#define ll long long
#define ld long double
#define req(i,h) for(int i = 0; i < h; i++)
#define req1(i,h) for(int i = 0; i <= h; i++)

using namespace std;


int main(void) {
    int n, count = 0;
    cin >> n;
    vector<int> d(n);
    req(i,n) cin >> d.at(i);
    sort(d.begin(), d.end());
    int fi =d.at(n/2 - 1);
    int se =d.at(n/2);
    for(int i = fi; i < se; i++) {
        count++;
    }
    cout << count << endl;
    return 0;
}






Measured memory_bytes: 640
#include<iostream>

using namespace std;

int main()
{
    int W,H,x,y,r;

    cin>>W>>H>>x>>y>>r;

    if(x>0 && x<W && y>0 && y<H){
        int minx,miny;
        minx = (x,W-x);
        miny = (y,H-y);
        if(minx >= r && miny >= r)
            cout<<"Yes\n";
        else
        {
            cout<<"No\n";
        }
        
    }else
    {
        cout<<"No\n";
    }
    
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int ans = -1;
    for(int i=1;i<=5;i++){
        int a;
        cin >> a;
        if(a==0) ans = i;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 3580
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <ctype.h>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
    if(b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

vector<int> prime(60000);
int k;

void primesearch(int x) {
    for(int i = 0;i < x;i++) prime[i] = i;
    prime[1]=0;
    for(int j = 2;j < x;j++) {
        for(int n = 2;j*n < x;n++) {
            k = j*n;
            prime[k] = 0;
        }
    }
}

int main() {
    int n,ans;
    primesearch(50001);
    while(1) {
        cin >> n;
        if(n==0) break;
        ans = 0;
        for(int p = 2;p < n;p++) {
            if(prime[p] != 0) {
                if(p > n-p) break; 
                if(prime[n-p] != 0) ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3036
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int > v;    
  int a,b,k;
  scanf("%d%d%d",&a,&b,&k);
  int i;
  int max=(a>=b)?a:b;
  for(i=1;i<=max;++i)
    {
        if((a%i)==0 && (b%i)==0)
            v.push_back(i);
          
    }
    
    sort(v.begin(),v.end());
    
    int s=v.size();
    printf("%d",v[s-k]);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct ioi
{
    int l,r;
}seg[300010];

bool cmp(ioi a,ioi b)
{
    return (a.r-a.l<b.r-b.l);
}

int n,m,res,f[300010];

void update(int u,int v)
{
    while (u<=m)
    {
        f[u]+=v;
        u+=u&-u;
    }
}

int get(int u)
{
    int v=0;
    while (u)
    {
        v+=f[u];
        u-=u&-u;
    }
    return v;
}

int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&(seg+i)->l,&(seg+i)->r);
    sort(seg+1,seg+n+1,cmp);
    res=n;
    int j=1;
    for (int i=1;i<=m;i++)
    {
        while (j<=n and seg[j].r-seg[j].l+1<i)
        {
            update(seg[j].l,1);
            update(seg[j].r+1,-1);
            res--;
            j++;
        }
        int cur=i,curres=res;
        while (cur<=m)
        {
            curres+=get(cur);
            cur+=i;
        }
        printf("%d\n",curres);
    }
}


Measured memory_bytes: 3712
// Exhausted?
// * frank_c1
// * 2017 / 11 / 16

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

#define lowbit(x) ((x) & (-x))

const int maxn = (int)(2e5) + 5;
int mx[maxn << 2], su[maxn << 2];
vector<int> nxt[maxn];
int n, m;

inline void addX(int x, int v) {
	mx[x] += v; su[x] += v;
}

inline void pd(int x) {
	if (su[x]) {
		addX(x << 1, su[x]); addX(x << 1 | 1, su[x]); su[x] = 0;
	}
}

inline void pu(int x) {
	mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}

int Q(int x, int l, int r, int p) {
	if (r <= p) return mx[x];
	pd(x); int mid = (l + r) >> 1, ret = Q(x << 1, l, mid, p);
	if (mid < p) ret = max(ret, Q(x << 1 | 1, mid + 1, r, p));
	return ret;
}

void M(int x, int l, int r, int p, int v) {
	if (p <= l) {
		addX(x, v); return;
	} pd(x); int mid = (l + r) >> 1;
	if (p <= mid) M(x << 1, l, mid, p, v); M(x << 1 | 1, mid + 1, r, p, v); pu(x);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		int l, r; scanf("%d%d", &l, &r);
		nxt[l].push_back(m - r + 1);
	} int ret = max(0, n - m);
	for (int i = 1; i <= m; ++i) M(1, 0, m, i, -1);
	for (int i = 0; i <= m; ++i) {
		for (int j = 0; j < (int)nxt[i].size(); ++j) M(1, 0, m, nxt[i][j], 1);
		ret = max(ret, Q(1, 0, m, m - i) - i);
	}
	return printf("%d\n", ret), 0;
}

Measured memory_bytes: 14080
S=input()
R="zyxwvutsrqponmlkjihgfedcba"
A=set(R)
if len(S)<=25:
    print(S+min(A-set(S)))
elif S==R:
    print(-1)
else:
    ok=set()
    while S:
        ok.add(S[-1])
        S=S[:-1]
        L=[s for s in ok if s > S[-1]]
        if L:
            print(S[:-1]+min(L))
            break


Measured memory_bytes: 3060
#include <stdio.h>
#include <limits.h>
#define null -1

typedef struct {
  int parent,left,right;
} node;

node tree[25];

void print(int);
void Preorder(int);
void Inorder(int);
void Postorder(int);

int n;

int main(){
  scanf("%d",&n);
  int i,j;
  int id;

  for(i=0;i<n;i++){
    tree[i].parent=tree[i].right=tree[i].left=null;
  }
  
  for(i=0;i<n;i++){
    scanf("%d",&id);
   
    scanf("%d%d",&tree[id].left,&tree[id].right);
    // printf("test;%d %d;\n",tree[id].left,tree[id].right);
    tree[tree[id].left].parent=id;
    tree[tree[id].right].parent=id;
    //  printf("test;%d %d;\n",tree[tree[id].left].parent,tree[tree[id].right].parent);
  }
  int root;
  for(i=0;i<n;i++){
    if(tree[i].parent==null)
      root=i;
  }
    print(root);
   
  return 0;
}

void print(int id){
  int i;
  printf("Preorder\n");
  
    Preorder(id);
  printf("\n");
  
  printf("Inorder\n");
  
    Inorder(id);
  printf("\n");
  
  printf("Postorder\n");
 
    Postorder(id);
  printf("\n");
}

void Preorder(int u){
  if(u==null) return;
  printf(" %d",u);
  Preorder(tree[u].left);
  Preorder(tree[u].right);
}

void Inorder(int u){
  if(u==null) return;
  Inorder(tree[u].left);
  printf(" %d",u);
  Inorder(tree[u].right);
}

void Postorder(int u){
  if(u==null) return;
  Postorder(tree[u].left);
  Postorder(tree[u].right);
  printf(" %d",u);
}



Measured memory_bytes: 2056
#include <iostream>
#include <queue>

using namespace std;

#define MAXSIZE 1024

char square[MAXSIZE][MAXSIZE];
int H, W, N;
int flag[MAXSIZE][MAXSIZE];
int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };

struct Node
{
	int x;
	int y;
};

int BFS(int &x, int &y, int n) {
	for (int i = 0; i < H; i ++)
	{
		for (int j = 0; j < W; j++)
		{
			flag[i][j] = -1;
		}
	}
	queue<Node> que;
	Node node;
	node.x = x;
	node.y = y;
	que.push(node);
	flag[x][y] = 0;
	while (!que.empty())
	{
		Node cur = que.front();
		que.pop();
		for (int i = 0; i < 4; i++)
		{
			x = cur.x + dir[i][0];
			y = cur.y + dir[i][1];
			if (square[x][y] - '0' == n)
			{
				return flag[cur.x][cur.y] + 1;
			}
			if (x >= 0 && x < H && y >= 0 && y < W && square[x][y] != 'X' && flag[x][y] == -1)
			{
				Node next;
				next.x = x;
				next.y = y;
				flag[x][y] = flag[cur.x][cur.y] + 1;
				que.push(next);
			}
		}
	}
	return 0;
}

int main() {
	int start_X, start_Y;
	int step = 0;
	cin >> H >> W >> N;
	for (int i = 0; i < H; i ++)
	{
		for (int j = 0; j < W;  j++)
		{
			cin >> square[i][j];
			if (square[i][j] == 'S')
			{
				start_X = i;
				start_Y = j;
			}
		}
	}
	for (int i = 1; i <= N; i++)
	{
		step += BFS(start_X, start_Y, i);
	}
	cout << step << endl;
	return 0;
}

Measured memory_bytes: 6312
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#include <functional>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<ll, ll, ll, ll> tlglglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
typedef unsigned int uint;
typedef unsigned long long ull;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<VV<T>>;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;
void yesno(bool ok, string yes = "Yes", string no = "No") {
    if (ok) {
        cout << yes << endl;
    } else {
        cout << no << endl;
    }
}

ll pow(ll v) {
    return v * v * v * v * v;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll X;
    cin >> X;
    REP(i, 0, 1 << 12) {
        REP(j, -i, i) {
            if (pow(i) - pow(j) == X) {
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 3592
N = int(input())
cards = [int(x) for x in input().split()]
ALICE = 0
BOB = 0
while cards:
  temp = max(cards)
  cards.remove(temp)
  ALICE+=temp
  if not(cards):
    break
  temp = max(cards)
  cards.remove(temp)
  BOB+=temp

print(ALICE - BOB)

Measured memory_bytes: 3060
#include<stdio.h>
#include<stdlib.h>
long long int solve(long long int, long long int, long long int, long long int*);
long long int check(long long int, long long int, long long int, long long int*);
main()
{
        long long int i, n, k, p = 0, w[100000];
        scanf("%lld %lld", &n , &k);
        //w = (long long int *)malloc(sizeof(long long int) * n);
        for (i = 0; i < n; i++) {
                scanf("%lld", &w[i]);
                if (p < w[i]) {
                        p = w[i];
                }
        }

        printf("%lld\n", solve(n, k, p, w));
}
long long int solve(long long int n, long long int k, long long int p, long long int *w)
{
        long long int i, mid, left = 1, right = n * p;
        while (left <= right ) {
                mid = (left + right) / 2;
                if(check(n, k, mid, w) >= n) {
                        right = mid - 1;
                } else {
                        left = mid + 1;
                }
        }
        return left;
}
long long int check(long long int n, long long int k, long long int p, long long int *w)
{
        int i, j = 0;
        for (i = 0; i < k; i++) {
                int s = 0;
                while (s + w[j] <= p) {
                        s += w[j++];
                }
                if (j == n) {
                        break;
                }
        }
        return j;
}



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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

class Prime {
public:
    Prime(ll n) {
        mPrimeTbl.clear();
        vector<bool> u(n, false);
        for (ll i = 2; i <= n; ++i) {
            if (u[i])
                continue;
            mPrimeTbl.push_back(i);
            for (ll p = i; p <= n; p += i)
                u[p] = true;
        }
    }

    ~Prime() {}

    ll num() {
        return static_cast<ll>(mPrimeTbl.size());
    }

    ll get(ll index) {
        return mPrimeTbl[index];
    }

private:
    vector<ll> mPrimeTbl;
};

int main() {
    ll N;
    cin >> N;
    Prime p(N);

    vector<ll> v(p.num(), 1);
    REP(i, N) {
        ll n = i + 1;
        REP(j, p.num()) {
            while (n % (p.get(j)) == 0) {
                n /= p.get(j);
                v[j]++;
            }
            if (n <= 1)
                break;
        }
    }

    ll ans = 1;
    REP(i, v.size()) {
        ans = (ans * v[i]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <algorithm>
#include <tuple>
using namespace std;
using T = tuple<int,int,int>;
bool isInfected[20000];
vector<T> V;

int main(){
    int N,M;
    while(cin>>N>>M,N){
        V.clear();
        for(int i=0;i<M;i++){
            int t,s,d;
            cin>>t>>s>>d;
            V.emplace_back(t,s-1,d-1);
        }
        sort(V.begin(), V.end());
        fill(isInfected,isInfected+20000,false);
        isInfected[0]=true;
        for(auto v:V){
            int t,s,d;
            tie(t,s,d)=v;
            if(isInfected[s])isInfected[d]=true;
        }

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

Measured memory_bytes: 3384
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
    ll N,sum=0,temp;
    cin >> N;
    temp = N;
    while(temp > 0){
        sum += temp%10;
        temp /= 10;
    }
    //cout << sum << endl;
    if(N%sum==0) cout << "Yes" << endl;
    else cout << "No" << endl;

}

Measured memory_bytes: 256
k=int(input())
a,b=map(int,input().split())
c=a//k
if (c+1)*k<=a:
  c+=1
d=b//k
if (d+1)*k<=b:
  d+=1
if c<d:
  print('OK')
else:
  if a%k==0:
    print('OK')
  else:
    print('NG')

Measured memory_bytes: 9192
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> make_v(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto make_v(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail&... tail) { cin >> head; read(tail...); }

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &out, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) out << e << delim[&e == &vec.back()];
    return out;
}
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N; read(N);
    print((N + 1) / 2);

    return 0;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main(){
    string S;cin>>S;
    rep(i,S.size())cout<<"x";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
S = sum(map(abs, A))

cnt = 0

for a in A:
    if a > 0:
        cnt += 1
        
if (len(A)-cnt)%2==0 or 0 in A:
    print(S)
else:
    print(S-2*min(map(abs, A)))

Measured memory_bytes: 20120
import math
from itertools import accumulate
from collections import Counter
import itertools
import functools


N = int(input())

strings = []
for i in range(N):
    strings.append(input())


strings = [''.join(sorted(i)) for i in strings]
c = Counter(strings)
count = 0
for i in c.values():
    if i > 1:
        count += (i * (i - 1)) / 2
print(int(count))

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

using namespace std;
using ll=long long;

void solve() {
    int n, p;
    cin >> n >> p;
    string s; cin >> s;

    if (p == 2 || p == 5) {
        ll res = 0;
        for (int i = 0; i < n; i++) {
            int x = s[i] - '0';
            if (x%p==0) {
                res += i + 1;
            }
        }
        cout << res; return;
    }

    reverse(s.begin(), s.end());
    map<int,int> mp;
    mp[0]++;
    int pw = 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int x = s[i]-'0';
        sum += pw * x; // 10^k = 0, p = 2,5
        sum %= p;
        pw *= 10; pw %= p;
        mp[sum]++;
    }
    ll res = 0;
    for (auto& _: mp) {
        ll x = _.second;
        res += x*(x-1)/2;
    }
    cout << res;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 916
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)

static const double PI=6*asin(0.5);
typedef complex<double> P;
typedef long long ll;


ll n;

int main(){
	while(cin>>n,n!=0){
		ll id[4005]={0};
		int a[8000]={0};
		
		int cou;
		rep(i,n){
			ll t1,t2,t3;
			cin>>t1>>t2>>t3;
			a[i]=t1;
			//if(id[t1]>0){
				id[t1]+=t2*t3;
			//}
			/*
			else{
				id[t1]=t2*t3;
			}
			*/
			cou=i;
		}
		bool f=true;
		rep(i,cou+1){
			if(id[a[i]]>=1000000){
				cout<<a[i]<<endl;
				id[a[i]]=0;
				f=false;
			}
		}
		if(f) cout<<"NA"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) ll((a).size())
#define out(a) cout<<(a)<<endl;
const ll inf=1e9;
const int MAX = 510000;
const ll MOD = 998244353;

int main(){
  ll n,a,b;cin>>n>>a>>b;
  if(b<a){cout<<0<<endl;return 0;}
  if(n==1&&a!=b){cout<<0<<endl;return 0;}
  ll l=(n-1)*a+b,r=(n-1)*b+a;
  cout<<r-l+1<<endl;
}


Measured memory_bytes: 3576
#include <stdio.h>

int main()
{
    int h1, m1, h2, m2, k;
    scanf("%d %d %d %d %d", &h1, &m1, &h2, &m2, &k);

    int period = ((h2 * 60) + m2) - ((h1 * 60) + m1) - k;
    printf("%d\n", period);
    return 0;
}

Measured memory_bytes: 1692
#include <iostream>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	int n;
	cin >> n;
	string s, s1;
	cin >> s >> s1;
	long long ans = 1;
	long long co = 3;
	for (int i = 0; i < n; i++) {
		if (s[i] == s1[i]) {
			if (i != 0) {
				if (s[i - 1] != s1[i - 1]) {
					continue;
				}
			}
			ans = ans * co % 1000000007;
		}
		else {
			if (i != 0) {
				if (s[i - 1] != s1[i - 1]) {
					ans = ans * 3 % 1000000007;
					i++;
					continue;
				}
			}
			ans = ans * co % 1000000007;
			ans = ans * (co - 1) % 1000000007;
			i++;
		}
		co = 2;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>

using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> p(n);
	for(int i=0;i<n;++i){
		cin >> p[i];
	}
	int res = 1;
	int min = p[0];
	for(int i=1;i<n;++i){
		if(p[i] <= min){
			res++;
			min = p[i];
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define mp(a,b) make_pair((a),(b))
#define eq ==

typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> pii;

// →↑←↓
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};


const double EPS = 1e-9;

struct Color{
    vector<double> colors;
    Color(double a,double b,double c){
        colors.push_back(a);
        colors.push_back(b);
        colors.push_back(c);
    }
    double operator*(Color& c){
        double ret = 0;
        for(int i=0;i<3;i++){
            double a = abs(c.colors[i]-colors[i]);
            ret += a*a;
        }
        return ret;
    }

    string toString(){
        stringstream ss;
        ss << "(" << colors[0] << " " << colors[1] << " " << colors[2] << ")";
        return ss.str();
    }
};

int main(){
    int N,M;
    cin >> N >> M;

    vector<Color> colors;
    for(int i=0;i<N;i++){
        double a,b,c;
        cin >> a >> b >> c;
        colors.push_back(Color(a,b,c));
    }

    stack<pair<int,vector<Color> > > stack;
    stack.push(make_pair(0,vector<Color>()));

    double r = -1;
    while(!stack.empty()){
        int l = stack.top().first;
        vector<Color> choose = stack.top().second;
        stack.pop();

        if(choose.size() == M){
            double ret = 0;
            for(int i=0;i<M;i++){
                for(int j=i+1;j<M;j++){
                    ret += choose[i]*choose[j];
                }
            }
            r = max(r,ret);
            continue;
        }
        for(int i=l;i<N-M+choose.size()+1;i++){
            vector<Color> cop = choose;
            cop.push_back(colors[i]);
            stack.push(make_pair(i+1,cop));
        }
    }
    cout << fixed << setprecision(10);
    cout << r << endl;
    return 0;
}

Measured memory_bytes: 1336
from collections import deque

N = int(input())
C = deque(list(input()))

cnt = 0

while len(C) > 1:
    if C[0] == 'W' and C[-1] == 'R':
        cnt += 1
        C.popleft()
        C.pop()
    else:
        if C[0] == 'R':
            C.popleft()
        if C[-1] == 'W':
            C.pop()

print(cnt)

Measured memory_bytes: 12380
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#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)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
ll dp[3300][3300];

int main(){
    int n;cin >> n;
    vl a(n);rep(i,n) cin >> a[i];
    for(int i=0;i<3300;i++) dp[i][i]=0;
    for(int width=1;width<=n;width++){
        for(int l=0;l+width<=n;l++){
            int r=width+l;
            if(width%2==n%2){
                dp[l][r]=max(dp[l+1][r]+a[l],dp[l][r-1]+a[r-1]);
            }
            else{
                dp[l][r]=min(dp[l+1][r]-a[l],dp[l][r-1]-a[r-1]);
            }
        }
    }
    cout << dp[0][n] << endl;
    return 0;
}

Measured memory_bytes: 84352
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()

	if N % 2 == 1:
		print(0)
		sys.exit()

	ans = 0
	base = 10
	while True:
		if base > N:
			break

		tmp = N // base
		ans += tmp
		base *= 5

	#nene = N // 10
	#manaka = N // 50
	#rinko = N // 250

	#tmp2 = goo(N)
	#print(tmp2)
	#print(nene)
	#print(manaka)
	#print(rinko)
	print(ans)

def goo(val):
	if val < 2:
		return 1
	else:
		bbb = goo(val-2)
		aaa = val * bbb
		#print("{} x {}".format(val,bbb))
		return aaa

if __name__ == "__main__":
	main()


Measured memory_bytes: 38384
#include <stdio.h>

int main(void)
{
	int n, tl;
	int i, j=0;
	int min_cost = 100000;
	int c, t;
	scanf("%d %d", &n, &tl);

	for(i=0;i<n;i++) {
		scanf("%d %d", &c, &t);
		if(t <= tl && c < min_cost) {
			min_cost = c;
		}
	}
	if(min_cost > 10000)
		printf("TLE\n");
	else
		printf("%d\n", min_cost);

	return 0;
}

Measured memory_bytes: 128
a, b, c, d = input()
op = ["+", "-"]

for op1 in op:
    for op2 in op:
        for op3 in op:
            check = a + op1 + b + op2 + c + op3 + d
            if eval(check) == 7:
                print(check + "=7")
                exit()

Measured memory_bytes: 61836
#include<bits/stdc++.h>
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define print(x) cout << (x) << endl;
#define printa(x, n) for(ll i = 0; i < n; i++) {cout << (x[i]) << " ";} cout << endl;
using namespace std;
using ll = long long;

int main(void) {
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    ll a[x], b[y], c[z];
    rep (i, x) cin >> a[i];
    rep (i, y) cin >> b[i];
    rep (i, z) cin >> c[i];

    sort(a, a + x, greater<ll>());
    sort(b, b + y, greater<ll>());
    sort(c, c + z, greater<ll>());

    vector<ll> ab;
    rep (i, x) rep (j, y) ab.push_back(a[i] + b[j]);
    
    sort(ab.rbegin(), ab.rend());

    vector<ll> ans;
    rep (i, min(k, x * y)) rep (j, z) ans.push_back(ab[i] + c[j]);

    sort(ans.rbegin(), ans.rend());

    rep (i, k) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 43364
//https://atcoder.jp/contests/dp/tasks/dp_k
#include<bits/stdc++.h>
using namespace std;
// dp[i] - TRUE if the first player wins if there are i stones remaining
// Note that ai are in increasing order
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> a(n);
    for(int& x : a) {
        scanf("%d", &x);
    }
    vector<bool> dp(k + 1);
    for(int stones = 0; stones <= k; ++stones) {
        for(int x : a) {
            if(stones >= x && !dp[stones-x]) {
                dp[stones] = true;
            }
        }
    }
    dp[k] ? cout<<"First" : cout<<"Second";
    return 0;
}

Measured memory_bytes: 256
N = int(input())
h = list(map(int, input().split()))

ans = 0
while sum(h) > 0:
  flag = False
  for i in range(N):
    if flag:
      if h[i] == 0:
        flag = False
        ans += 1
      else:
        h[i] -= 1
        if i == N-1:
          ans += 1
    else:
      if h[i] > 0:
        h[i] -= 1
        flag = True
        if i == N-1:
          ans += 1
          flag = False
print(ans)

Measured memory_bytes: 9200
n, p = map(int, input().split())
A = list(map(int, input().split()))

f = 0
for a in A:
    if a%2:
        f = 1
        break

if f:
    ans = 2**(n-1)
else:
    if p:
        ans = 0
    else:
        ans = 2**n
print(ans)

Measured memory_bytes: 3060
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long N = sc.nextInt();
    long total =0;
    for (long i =0; i<=N; i++) {
      if (i % 3 != 0 && i % 5 != 0 ) {
        total += i;
      }
    }
    System.out.println(total);
  }
}

Measured memory_bytes: 27120
import math

def dictcheck(dict):
    min = 0
    for k,v in dict.items():
        if k == 1:
            min = v
            break
        elif min == 0:
            min=(int(k)-1)+(int(v)-1)
        elif min > (int(k)-1)+(int(v)-1):
            min = (int(k)-1)+(int(v)-1)
        else:
            continue
    print(min)

def main():
    N = int(input())
    i = 2
    tmpdict= {}
    while i <= math.sqrt(N):
        if N % i == 0:
            tmpdata = {i:N/i}
            tmpdict.update(tmpdata)
            i+=1
        else:
            i+=1
    if len(tmpdict)==0:
        tmpdata = {1:N-1}
        tmpdict.update(tmpdata)
#    print(tmpdict)
    dictcheck(tmpdict)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3512