akhauriyash/Code-Regression huggingface dataset:
use proconio::input;

use proconio::marker::{Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused)]
const ALPHA_SMALL: [char; 26] = [
    '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',
];
#[allow(unused)]
const ALPHA: [char; 26] = [
    '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',
];
fn main() {
    input!(N: usize, K: i64);
    input!(P: [Usize1; N]);
    input!(C: [i64; N]);
    let mut ans = std::i64::MIN;

    let p = parse(&P, &C);
    for g in &p {
        let L = g.len();
        let cs = calc(g, K);
        let sum = cs[L - 1];
        let m = K as usize % L;
        let n = K / L as i64;
        //println!("{:?}", cs);
        // for (i, &cost) in cs.iter().enumerate() {
        //     ans = max(ans, cost);
        //     if sum <= 0 || (K as usize) < L {
        //         continue;
        //     }
        //     for j in 1..=(K as usize % L) {
        //         ans = max(ans, sum * (K / L as i64) + cs[j - 1]);
        //     }
        //     ans = max(ans, sum * (K / L as i64));
        // }
        if sum <= 0 {
            for &cost in &cs {
                ans = max(ans, cost);
            }
        } else {
            for i in 0..=m {
                if i == 0 {
                    ans = max(ans, sum * n);
                } else {
                    ans = max(ans, sum * n + cs[i - 1]);
                }
            }
            if n > 0 {
                for i in 0..L {
                    if i == 0 {
                        ans = max(ans, sum * (n - 1));
                    } else {
                        ans = max(ans, sum * (n - 1) + cs[i - 1]);
                    }
                }
            }
        }
    }

    println!("{}", ans);
    //println!("{:?}", p);
}

fn calc(g: &Vec<(usize, i64)>, K: i64) -> Vec<i64> {
    let mut ret = vec![std::i64::MIN; g.len()];
    let L = g.len();
    for start in 0..L {
        let mut cost = 0;
        for pos in 0..L {
            cost += g[(start + pos) % L].1;
            ret[pos] = max(ret[pos], cost);
        }
    }

    ret
}

//単一視点から目的のノードまでの最短距離、ただし全ての辺の重みが等しいグラフに限る
fn parse(g: &Vec<usize>, cost: &Vec<i64>) -> Vec<Vec<(usize, i64)>> {
    let N = g.len();
    let mut ret = Vec::new();
    let mut visit = vec![false; N];

    for start in 0..N {
        if visit[start] {
            continue;
        }
        let mut now = start;
        let mut h = Vec::new();
        while !visit[now] {
            visit[now] = true;
            h.push((now, cost[g[now]]));
            now = g[now];
        }

        ret.push(h);
    }

    ret
}


Measured memory_bytes: 2464
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = (int)1e9;
const ll  inf = (ll)1e18;
const int mod = 1000000007;
const int MAX_N = 100010;
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	ll n, x, y;
	cin >> n >> x >> y;

	vector<ll> cnt(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			int ij = j - i;
			int ixyj = abs(x - i) + 1 + abs(y - j);
			cnt[min(ij, ixyj)]++;
		}
	}

	for (int i = 1; i < n; i++) {
		out(cnt[i]);
	}

	return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
score = -INF
for st in range(n):
    lap_cn = 0
    lap_sc = 0
    nx = st
    while True:
        lap_cn += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break
    lap_sc = max(0, lap_sc)

    sum_sc = 0
    k_cn = 0
    while True:
        k_cn += 1
        if k < k_cn: break
        sum_sc += C[nx]
        score = max(score, sum_sc + lap_sc * ((k - k_cn) // lap_cn))
        nx = P[nx]
        if nx == st: break

print(score)


Measured memory_bytes: 74180
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define str string
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define all(x) x.begin(),x.end()
int main(){
  int A,B,C;
  cin>>A>>B>>C;
  if(B-A==C-B)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;

double EPS=1e-9;
int INF=1000000005;
long long INFF=1000000000000000005ll;
double PI=acos(-1);
int dirx[8]={ -1, 0, 0, 1, -1, -1, 1, 1 };
int diry[8]={ 0, 1, -1, 0, -1, 1, -1, 1 };
const ll MOD = 1000000007;

#define DEBUG fprintf(stderr, "====TESTING====\n")
#define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
#define OUT(x) cout << x << endl
#define OUTH(x) cout << x << " "
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define READ(x) for(auto &(z):x) cin >> z;
#define FOR(a, b, c) for (int(a)=(b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a)=(b); (a) <= (c); ++(a))
#define FORD(a, b, c) for (int(a)=(b); (a) >= (c); --(a))
#define FORSQ(a, b, c) for (int(a)=(b); (a) * (a) <= (c); ++(a))
#define FORC(a, b, c) for (char(a)=(b); (a) <= (c); ++(a))
#define EACH(a, b) for (auto&(a) : (b))
#define REP(i, n) FOR(i, 0, n)
#define REPN(i, n) FORN(i, 1, n)
#define MAX(a, b) a=max(a, b)
#define MIN(a, b) a=min(a, b)
#define SQR(x) ((ll)(x) * (x))
#define RESET(a, b) memset(a, b, sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PERMUTE next_permutation
#define TC(t) while (t--)
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)


void solve() {

}

int main()
{
    FAST_INP;
//    #ifndef ONLINE_JUDGE
//    freopen("input.txt","r", stdin);
//    freopen("output.txt","w", stdout);
//    #endif

//    int tc; cin >> tc;
//    TC(tc) solve();
	string s;
	cin >> s;
	if(s[0]==s[1]||s[1]==s[2]||s[2]==s[3]) OUT("Bad");
	else OUT("Good");

    return 0;
}

Measured memory_bytes: 3572
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
	int n; cin >> n;
	string s; cin >> s;
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (i == n - 1 && s[i] != s[i - 1]) {
			++cnt; break;
		}
		if (s[i] != s[i+1])++cnt;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 512
from itertools import permutations
N, M, R = map(int, input().split())
rs = map(lambda x: int(x) - 1, input().split())
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    v1, v2, d = map(int, input().split())
    dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
for i in range(N):
    dist[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 10**9
for r in permutations(rs):
    t = 0
    for i in range(R-1):
        t += dist[r[i]][r[i+1]]
        if t > 10**9:
            break
    ans = min(t, ans)
print(ans)

Measured memory_bytes: 47576
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using ll = long long;
#define ull unsigned ll
#define endl "\n"
#define vi vector<int>
#define vl vector<ll>
#define all(v) (v).begin(),(v).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pll pair<ll, ll>
#define ppi pair<int, pii>
#define vpi vector<pii>
#define vpl vector<pll>
#define mt make_tuple
#define eb emplace_back
using namespace std;

const ll N = 1e6 + 5, mod = 1e9 + 7;
const ll inf = 1e18;

struct cmp{
    bool operator() (pii a, pii b){
        if(a.F == b.F) return a.S < b.S;
        return a.F > b.F;
    }
};

ll power(ll x, ll p){
    ll r = 1ll;
    x = x % mod;
    while(p > 0){
        if(p & 1) r = (r * x) % mod;
        p = p >> 1;
        x = (x * x) % mod;
    }
    return r;
}
int n;
vi a;
bool isprime[N];
void solve(){
    int n;
    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int g = a[0];
    for(int i = 1; i < n; i++){
        g = __gcd(g, a[i]);
        if(g == 1) break;
    }
    if(g != 1){
        cout << "not coprime" << endl;
        return;
    }
    sort(all(a));
    for(int i = 2; i < N; i++){
        isprime[i] = 1;
    }
    for(int i = 2; i * i < N; i++){
        if(isprime[i]){
            for(int j = i * i; j < N; j += i){
                isprime[j] = 0;
            }
        }
    }
    vi v;
    for(int i = 2; i < N; i++){
        if(isprime[i]){
            v.pb(i);
        }
    }
    for(int i : v){
        int j = i;
        int cnt = 0;
        while(j < N){
            int k = upper_bound(all(a), j) - a.begin();
            k--;
            if(a[k] == j){
                cnt++;
            }
            j += i;
        }
        if(cnt > 1){
            cout << "setwise coprime" << endl;
            return;
        }
    }
    cout << "pairwise coprime" << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //cout.tie(0);
    /*#ifndef ONLINE_JUDGE
        freopen("Input.txt", "r", stdin);
    #endif*/
    //freopen("running_on_fumes_chapter_1_input (1).txt", "r", stdin);
    //freopen("Output.txt", "w", stdout);
    int t = 1, p;
    //cin >> t;
    for(p = 1; p <= t; p++){
        //cout << "Case #" << p << ": ";
        solve();
    }
    return 0;
}


Measured memory_bytes: 8764
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T> >;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repb(i, n) for(ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define reprb(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(unsigned long long x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
template<class T>bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

void pr(ll n){
    cout << n << endl;
    exit(0);
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n;
    cin >> n;
    vll t(n);
    rep(i, n){
        cin >> t[i];
    }
    vll a(n);
    rep(i, n){
        cin >> a[i];
    }
    vll ans1(n, INF);
    vll ans2(n, INF);
    vi ansd1(n, 0);
    vi ansd2(n, 0);
    rep(i, n){
        if(i == 0 || t[i] > t[i-1]){
            chmin(ans1[i], 1ll);
            ansd1[i] = 1;
        }else{
            chmin(ans1[i], t[i]);
        }
    }
    repb(i, n){
        if(i == n-1 || a[i] > a[i+1]){
            chmin(ans2[i], 1ll);
            ansd2[i] = 1;
        }else{
            chmin(ans2[i], a[i]);
        }
    }
    rep(i, n){
        if(ansd1[i] == 1 && ansd2[i] == 1 && t[i] != a[i]){
            pr(0);
        }
        if(ansd1[i] == 1 && ansd2[i] == 0 && t[i] > a[i]){
            pr(0);
        }
        if(ansd1[i] == 0 && ansd2[i] == 1 && t[i] < a[i]){
            pr(0);
        }
    }
    ll ansm = 1;
    rep(i, n){
        ansm *= min(ans1[i], ans2[i])%MOD;
        ansm %= MOD;
    }
    cout << ansm << endl;
    return 0;
}

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

#define ll long long

int main()
{
    ll n,a,b;
    scanf("%lld %lld %lld",&n,&a,&b);
    if(a==0)
        cout<<0<<endl;
    else if(b==0)
        cout<<n<<endl;
    else if(a>=n)
        cout<<n<<endl;
    else
    {
        if(n%(a+b)==0)
            printf("%lld\n",(n/(a+b))*a);
        else
        {
            ll r=n-((n/(a+b))*(a+b));
            if(r<a)
                printf("%lld\n",(n/(a+b))*a+r);
            else
                printf("%lld\n",(n/(a+b))*a+a);
        }
    }
}


Measured memory_bytes: 256
n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
inf=1000000001
x=[[inf,v_sub],[inf],[inf],[inf]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    z=w_sub-w0
    x[z].append(v_sub)
for i in range(4):
    x[i].sort(reverse=True)
    x[i][0]=0
    l_sub=len(x[i])
    for j in range(1,l_sub):
        x[i][j]+=x[i][j-1]

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)


Measured memory_bytes: 3064
#include <iostream>

const int N = (int) (1e5 + 10);
const int INF = (int) (2.1e9);

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

#if DEBUG_ON
    freopen("input", "r", stdin);
#endif

    int a, b, m;
    std::cin >> a >> b >> m;
    int fridge[N], microwave[N];
    int minFridge = INF, minMicrowave = INF;
    for (int i = 0; i < a; ++i) {
        std::cin >> fridge[i];
        if (fridge[i] < minFridge) {
            minFridge = fridge[i];
        }
    }
    for (int i = 0; i < b; ++i) {
        std::cin >> microwave[i];
        if (microwave[i] < minMicrowave) {
            minMicrowave = microwave[i];
        }
    }
    int res = minFridge + minMicrowave;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        std::cin >> x >> y >> c;
        --x; --y;
        int cost = fridge[x] + microwave[y] - c;
        if (cost < res) {
            res = cost;
        }
    }
    std::cout << res << '\n';
    return 0;
}


Measured memory_bytes: 1024
/* Header {{{ */
#include <bits/stdc++.h>
using namespace std;

typedef long long readtype;
typedef long long var;
typedef long double let;

readtype read() {
  readtype a = 0, c = getchar(), s = 0;
  while (!isdigit(c)) s |= c == '-', c = getchar();
  while (isdigit(c)) a = a * 10 + c - 48, c = getchar();
  return s ? -a : a;
}

#ifdef LOCAL_LOGGER
#define logger(...) fprintf(stderr, __VA_ARGS__)
#define abortif(v, ...) if (v) {logger("Error in Line %d, Function '%s()'.\nInfo: ", __LINE__, __FUNCTION__); logger(__VA_ARGS__); exit(0);}
#else
#define logger(...);
#define abortif(v, ...);
#endif
/* }}} */

const let EPS = 1e-8;

int sign(let x) { return (x < -EPS) ? -1 : (x > EPS ? 1 : 0); }

struct Point {
  let x, y;
  let dist() {
    return sqrt(x * x + y * y);
  }

  friend Point operator - (Point a, Point b) {
    return (Point) {a.x - b.x, a.y - b.y};
  }

  Point operator ~ () {
    return (Point) {x, -y};
  }

  Point Rotate(let sink, let cosk) {
    return (Point) {
      x * cosk - y * sink, x * sink + y * cosk
    };
  }

  Point Rotate(Point k) {
    let z = k.dist();
    if (!z) return *this;
    return Rotate(k.y / z, k.x / z);
  }
};

typedef Point Vec;

struct Circle {
  Point o;
  let r;

  friend Circle operator - (Circle a, Vec b) {
    return (Circle) {a.o - b, a.r};
  }

  Circle Rotate(Vec v) {
    return (Circle) {o.Rotate(v), r};
  }

  friend int Relate(Circle a, Circle b) {
    Circle c = (b - a.o).Rotate(~(b.o - a.o));
    if (sign(c.o.x + c.r - a.r) < 0 && sign(c.o.x - c.r + a.r) > 0) return 0;
    if (sign(c.o.x + c.r - a.r) > 0 && sign(c.o.x - c.r + a.r) < 0) return 0;
    if (sign(c.o.x + c.r - a.r) == 0 || sign(c.o.x - c.r + a.r) == 0) return 1;
    if (sign(c.o.x - c.r - a.r) == 0 || sign(c.o.x + c.r + a.r) == 0) return 3;
    if (sign(c.o.x - c.r - a.r) > 0 || sign(c.o.x + c.r + a.r) < 0) return 4;
    return 2;
  }
};

Point ReadPoint() {
  Point p;
  scanf("%Lf%Lf", &p.x, &p.y);
  return p;
}

Circle ReadCircle() {
  Circle c;
  c.o = ReadPoint();
  scanf("%Lf", &c.r);
  return c;
}
int main() {
// #ifndef ONLINE_JUDGE
//   freopen("CGL_7_A.in", "r", stdin);
//   freopen("CGL_7_A.out", "w", stdout);
// #endif
// #ifdef LOCAL_LOGGER
//   freopen("CGL_7_A.log", "w", stderr);
// #endif
  Circle a = ReadCircle(), b = ReadCircle();
  printf("%d\n", Relate(a, b));
  return 0;
}

/* ==== Makefile ==== {{{
CompileAndRun:
	make Compile
	make Run

Compile:
	g++ -o CGL_7_A CGL_7_A.cpp -g -Wall -DLOCAL_LOGGER

CompileUF:
	g++ -o CGL_7_A CGL_7_A.cpp -g -Wall -DLOCAL_LOGGER -fsanitize=undefined

Run:
	./CGL_7_A < CGL_7_A.in > CGL_7_A.out
==================
}}} */



Measured memory_bytes: 3244
// IO
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm
#include <algorithm>
#include <cmath>
#include <numeric>

// container
#include <vector>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>

// others
#include <random>
#include <limits>
#include <functional>
#include <ctime>
#include <cassert>

// type alias
using lint = long long;
using ldouble = long double;
template <class T>
using greater_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T>>;


/* ----- class ----- */

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
using Edges = std::vector<Edge<Cost>>;

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;


/* ----- debug ----- */

#if __has_include("../setting/source/debug.hpp")
#include "../setting/source/debug.hpp"
#endif


/* ----- short functions ----- */

template <class T>
inline T sq(T a) { return a * a; }

template <class T>
inline T iceil(T n, T d) { return (n + d - 1) / d; }

template <class T>
T gcd(T a, T b) {
    while (b > 0) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

template <class T, class U>
T ipow(T b, U n) {
    T ret = 1;
    while (n > 0) {
        if (n & 1) ret *= b;
        n >>= 1;
        b *= b;
    }
    return ret;
}

// 0-indexed
template <class T, class U>
inline T kthbit(T a, U k) { return (a >> k) & 1; }

template <class T, class U>
inline T mask(T a, U k) { return a & ((1 << k) - 1); }

template <class T>
std::map<T, int> compress(std::vector<T>& v) {
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());

    std::map<T, int> rev;
    for (int i = 0; i < v.size(); ++i) rev[v[i]] = i;
    return rev;
}

template <class T>
T Vec(T v) { return v; }

template <class T, class... Ts>
auto Vec(size_t l, Ts... ts) {
    return std::vector<decltype(Vec<T>(ts...))>(l, Vec<T>(ts...));
}


/* ----- constants ----- */

// const int INF = std::numeric_limits<int>::max() / 3;
// const lint INF = std::numeric_limits<lint>::max() / 3;
// const ldouble PI = acos(-1);
// const ldouble EPS = 1e-10;
// std::mt19937 mt(int(std::time(nullptr)));


using namespace std;

inline lint calc(lint X, lint C, lint D) {
    return X - X / C - X / D + X / (C / gcd(C, D) * D);
}

int main() {
    lint A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << calc(B, C, D) - calc(A - 1, C, D) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }
constexpr int sum(int x) { return (x * (x + 1)) / 2; }

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;
}
ll factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i);
    }
    return rtn;
}
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll x; cin >> x;
    int t = 1;
    while (sum(t) < x) {
        t++;
    }
    if (sum(t) > x && sum(t) - x < t) {
        cout << t;
        return 0;
    }
    cout << t;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
#define REP(i,j,n) for (int i=j;i<(n);i++)
#define RREP(i,n) for (int i = n; 0<i;i--)
#define print(out) cout<< out  << "\n";
#define mod 1000000007
const int INF = 1e9;
typedef pair<ll,ll> P;

class UnionFindTree {
    std::vector<int> tree;
public:
    UnionFindTree(size_t n): tree(n, -1) {}
    size_t find_root(size_t v) {
        if (tree[v] < 0) return v;
        return tree[v] = find_root(tree[v]);
    }
    bool unite(size_t x, size_t y) {
        x = find_root(x);
        y = find_root(y);
        if (x == y) return false;
        if (rank(x) < rank(y)) std::swap(x, y);
        tree[x] += tree[y];
        tree[y] = x;
        return true;
    }
    bool connected(size_t x, size_t y) {
        return find_root(x) == find_root(y);
    }
    size_t rank(size_t v) {
        return -tree[find_root(v)];
    }
};

int main(){
  int N,K,L;cin>>N>>K>>L;
  int P[K],Q[K],R[L],S[L];
  REP(k,0,K)cin>>P[k]>>Q[k];
  REP(l,0,L)cin>>R[l]>>S[l];
  
  UnionFindTree rd(N);
  UnionFindTree rrd(N);

  REP(k,0,K)rd.unite(P[k]-1,Q[k]-1);
  REP(l,0,L)rrd.unite(R[l]-1,S[l]-1);

  map<pair<int,int>,int> mp;
  REP(i,0,N)mp[make_pair(rd.find_root(i),rrd.find_root(i))]++;
  REP(i,0,N){
    cout<<mp[make_pair(rd.find_root(i),rrd.find_root(i))];
    if(i==N-1){
      cout<<"\n";
      return 0;
    }
    cout<<" ";
  }

}

Measured memory_bytes: 15104
// Author : Nachiket Kanore
// Institute : PICT, Pune

/* It does not matter how slowly you go as long as you do not stop.*/

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'
#define rep(x,s,e) for(int x=s;x<=(e);x++)
#define repn for(int x=0;x<n;x++)
#define rep1n for(int x=1;x<=n;x++)
#define rep1m for(int y=1;y<=m;y++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define precise(x) cout << fixed << setprecision(x)
#define bits(x) __builtin_popcount(x)
#define pb push_back
#define mp make_pair
#define test int t; cin>>t; while(t--)
#define FAST                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)

typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef pair<int,int> pii;


void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}


template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define see(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define see(x...)
#endif

const int inf = 1e18;
const int N = 1005;


int32_t main(){
    FAST;

    for(int x=1;x<=3;x++){
        for(int y=1;y<=3;y++){
            char ch;    cin >> ch;
            if(x == y)
                cout << ch;
        }
    }

    return 0;
}




Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

use std::cmp;

fn main() {
    input! {
        N: usize,
        A: [i64; N]
    }
    let mut ans = i64::max_value();
    for a in A.iter(){
        let mut a: i64 = *a;
        let mut t = 0i64;
        while a % 2 == 0{
            t += 1;
            a /= 2;
        }
        ans = cmp::min(t, ans)
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
const ll LINF = 0x1fffffffffffffff;
const ll MOD = 1000000007;
#define name3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0;i<(n);++i)
#define rep2(i,n) for(ll i=0;i<(n);++i)
#define rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) name3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define each(i,a) for(auto &i : a)
#define sum(a) accumulate(all(a), 0LL)
#define all(i) begin(i), end(i)
template<class T, class U> inline bool chmin(T &a, const U &b){ if(a > b) { a = b; return 1; } else return 0; }
template<class T, class U> inline bool chmax(T &a, const U &b){ if(a < b) { a = b; return 1; } else return 0; }


ll n;
struct T{
    ll cnt[800] = {};
    T operator*(const T& a) const {
        T ans;
        rep(n)rep(j,n)ans.cnt[(i+j)%n]+=cnt[i]*a.cnt[j]%MOD;
        each(i,ans.cnt)i%=MOD;
        return ans;
    }
    T pow(ll x) const {
        T ans, a = *this;
        ans.cnt[0]  = 1;
        while(x){
            if(x & 1) ans = ans * a;
            a = a * a;
            x >>= 1;
        }
        return ans;
    }
};
int main(){
    ll m, k;
    cin >> n >> m >> k;
    T ans;
    ans.cnt[0] = 1;
    rep(m){
        ll p;
        cin >> p;
        ans.cnt[p % n]++;
    }
    ans = ans.pow(k);
    rep(n) cout << ans.cnt[i] << endl;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define lb(s,x) (lower_bound(all(s),x)-s.begin())
#define ub(s,x) (upper_bound(all(s),x)-s.begin())
#define uniq(a) a.erase(unique(all(a)),a.end())
#define bit(k) (1LL<<(k))
const int INF = 1e9;

#define debug(x) cerr<<(#x)<<": "<<(x)<<endl
template<class T,class U>
ostream& operator<<(ostream& o, const pair<T,U> &p){
    o<<"("<<p.first<<", "<<p.second<<")";
    return o;
}
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }


typedef complex<double> Point;
typedef vector<Point> VP;
#define X real()
#define Y imag()
const double EPS = 1e-9;
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define ps_edge(PS,i) PS[i],PS[(i+1)%PS.size()]

namespace std {
    bool operator<(const Point a, const Point b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

double dot(Point a, Point b) {
    return a.X*b.X + a.Y*b.Y;
}

double cross(Point a, Point b) {
    return a.X*b.Y - a.Y*b.X;
}

int ccw(Point a, Point b, Point c) {
    b -= a;  c -= a;
    if (cross(b,c) >  EPS) return +1;  // counter clockwise
    if (cross(b,c) < -EPS) return -1;  // clockwise
    if (dot(b,c)   < -EPS) return +2;  // c--a--b on line
    if (norm(b) < norm(c)) return -2;  // a--b--c on line or a==b
    return 0;                          // a--c--b on line or a==c or b==c
}

// 点集合を含む最小の円の中心
Point minEnclosingCircle(const VP& ps) {
    Point c;
    double move = 0.5;
    rep(i,39) {  // 2^(-39-1) \approx 0.9e-12
        rep(t,100) {
            double max = 0;
            int k = 0;
            rep (j, ps.size()) if (max < norm(ps[j]-c)) {
                max = norm(ps[j]-c);
                k = j;
            }
            c += (ps[k]-c) * move;
        }
        move /= 2;
    }
    return c;
}


int main(void){
    int n;
    cin >> n;
    VP ps(n);
    rep(i,n){
        double x, y;
        cin >> x >> y;
        ps[i] = Point(x,y);
    }
    Point c = minEnclosingCircle(ps);
    double r = 0;
    rep(i,n){
        r = max(r, abs(c-ps[i]));
    }
    printf("%.20f\n",r);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[] count = new int[n];
		
		for(int i = 0; i < n-1; i++)
		{
			int cur = sc.nextInt()-1;
			count[cur]++;
		}
		
		for(int i = 0; i < n; i++)
		{
			System.out.println(count[i]);
		}
	}

}


Measured memory_bytes: 61900
#include <bits/stdc++.h>
#include <unistd.h>
#define ll long long
#define inf 1000000007
#define inf16 0x3f3f3f3f
#define INF 1000000000000000007LL
#define VI vector<int>
#define VPII vector<pair<int, int> >
#define VLL vector<ll>
#define PII pair<int, int>
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
using namespace std;

#define int ll

int h, w, n, k, ans;

int pot[50*50];

int query(int y1, int y2, int x1, int x2)
{
	cout << "? " << y1 << " " << x1 << " " << y2 << " " << x2 << endl;
	int ans;
	cin >> ans;
	return ans;
}

void solve(int y1, int y2, int x1, int x2, int cnt, int split)
{
	if(cnt==0)
		return;

	if(cnt==(y2-y1+1)*(x2-x1+1))
	{
		for(int i = y1; i <= y2; ++i)
		{
			for(int j = x1; j <= x2; ++j)
			{
				ans += pot[i*w+j];
				ans %= k;
			}
		}

		return;
	}

	if(y1!=y2)//split)
	{
		int m = (y1+y2)/2;
		int h = query(y1, m, x1, x2);
		solve(y1, m, x1, x2, h, split^1);
		solve(m+1, y2, x1, x2, cnt-h, split^1);
	}
	else
	{
		int m = (x1+x2)/2;
		int h = query(y1, y2, x1, m);
		solve(y1, y2, x1, m, h, split^1);
		solve(y1, y2, m+1, x2, cnt-h, split^1);
	}
}

int32_t main()
{
	cin >> h >> w >> n >> k;

	pot[0] = 1;

	for(int i = 1; i < 50*50; ++i)
	{
		pot[i] = pot[i-1]*2%k;
	}

	for(int j = 0; j < w; j += 10)
	{
		solve(0, h-1, j, min(j+9, w-1), query(0, w-1, j, min(j+9, w-1)), 1);
	}

	/*for(int i = 0; i < h; i += 5)
	{
		for(int j = 0; j < w; j += 5)
		{
			solve(i, i+4, j, j+4, query(i, i+4, j, j+4), 1);
		}
	}*/

	//solve(0, h-1, 0, w-1, n, 1);

	cout << "! " << ans << endl;
}

Measured memory_bytes: 720
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a)  (a).begin(),(a).end()


int main(){
    int N, A;
    cin >> N;
    cin >> A;
    cout << (N * N - A) << endl;
}

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

int d[10][10];
int V = 10;

void warshall_floyd(){
  for(int k = 0;k < V;k++){
    for(int i = 0;i < V;i++){
      for(int j = 0;j < V;j++){
        d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
      }
    }
  }
}

int main(){
  int h,w;
  cin >> h >> w;
  for(int i = 0;i < 10;i++){
    for(int j = 0;j < 10;j++){
      cin >> d[i][j];
    }
  }
  int cost = 0;
  warshall_floyd();
  for(int i = 0;i < h;i++){
    for(int j = 0;j < w;j++){
      int a;
      cin >> a;
      if(a == -1) continue;
      cost += d[a][1];
    }
  }
  cout << cost << endl;
}
  

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

using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7;
vector<ll> fact;

void init_fact(int n) {
    fact = vector<ll>(n);
    fact[0] = 1;
    for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i % MOD;
}

ll calc_pow(ll x, ll pow) {
    if (pow == 0) return 1;
    ll a = calc_pow(x, pow / 2);
    a = a * a % MOD;
    if (pow % 2 == 1) a *= x;
    return a % MOD;
}

ll calc_div(ll a, ll b) {
    return a * calc_pow(b, MOD - 2) % MOD;
}

ll calc_comb(ll n, ll r) {
    if (n < r)return 0;
    return calc_div(fact[n], fact[r] * fact[n - r] % MOD);
}

int main() {
    init_fact(3000000);
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;

    ll ret = calc_comb(c1 + r1, r1);
    ret -= calc_comb(r1 + c2 + 1, r1), ret = (ret + MOD) % MOD;
    ret -= calc_comb(c1 + r2 + 1, r2 + 1), ret = (ret + MOD) % MOD;
    ret += calc_comb(c2 + 1 + r2 + 1, r2 + 1), ret %= MOD;
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 23680
/*
 _ _ _   _    _   _    _   _ _ _   _    _   _ __ _   __       __
|  _ _| | |  | | | |  | | |  _  | | |  | | |  __  | |   \   /   |
| |_ _  | |__| | | |  | | | |_| | | |__| | | |__| | | |\ \_/ /| |
|_ _  | |  __  | | |  | | |  _ <  |  __  | |  __  | | | \   / | |
 _ _| | | |  | | | |__| | | |_| | | |  | | | |  | | | |  \_/  | |  _   _   _
|_ _ _| |_|  |_| |_ __ _| |_ _ _| |_|  |_| |_|  |_| |_|       |_| |_| |_| |_|

*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi first
#define se second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(a) cout << #a << " = " << a << " ";
#define endl "\n"
const int MOD=1e9 + 7;
const int N=1000100;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){  
                                                        for (auto &v : vec) is >> v; return is; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

void solve(){
    long n,d,a;
    cin>>n>>d>>a;
    vector< pair<long,long> > v(n); 
    for(int i=0;i<n;i++){
        cin>>v[i].first>>v[i].second;
    }
    sort(v.begin(),v.end());
    vector<long>  x(n),h(n),cnt(n+1,0);
    for(int i=0;i<n;i++){
        x[i]=v[i].first; h[i]=v[i].second;
    }
    ll ans=0,id=0;
    for(int i=0;i<n;i++){
        if(i)
            cnt[i]+=cnt[i-1];

        h[i]-=cnt[i]*a;
        if(h[i]<=0)
            continue;
        long num=(h[i]+a-1)/a;
        ans+=num;
        cnt[i+1]+=num;
        while(id<n && x[id]-x[i]<=2*d)
            id++;
        cnt[id]-=num;
    }
    cout<<ans<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long int t = 1;
    // cin>>t;
    for (long int tt = 1; tt <= t; tt++) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 11116
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        long[] A = new long[N + 1];
        long[] B = new long[N];

        for (int i = 0 ; i < N + 1 ; i++) {
            A[i] = scanner.nextLong();
        }

        for (int i = 0 ; i < N ; i++) {
            B[i] = scanner.nextLong();
        }

        long answer = 0;
        for (int i = 0 ; i < N ; i++) {
            answer += Math.min(A[i], B[i]);
            B[i] = B[i] - Math.min(A[i], B[i]);
            answer += Math.min(A[i + 1], B[i]);
            A[i + 1] -= Math.min(A[i + 1], B[i]);
        }

        System.out.println(answer);
      }
}


Measured memory_bytes: 61284
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
  int N, X, Y;
  cin >> N >> X >> Y;
  --X;
  --Y;
  vector<int> ans(N);
  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      int dist = j - i;
      dist = min(dist, abs(i - X) + abs(j - Y) + 1);
      dist = min(dist, abs(i - Y) + abs(j - X) + 1);
      ans[dist] += 1;
    }
  }
  for (int k = 1; k < N; ++k) {
    cout << ans[k] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void)
{
	int n;
	
	scanf("%d", &n);
	scanf("%*c");
	while (n-- > 0){
		char str[1024] = {0};
		int i;
		
		fgets(str, 1005, stdin);
		for (i = strlen(str) - 2; i > 5; i--){
			if (strncmp(str + i - 6, "Hoshino", 7) == 0){
				str[i] = 'a';
			}
		}
		printf(str);
	}
	
	return 0;
}

Measured memory_bytes: 592
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


A, B, C = map(int, input().split())
K = int(input())
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k > K:
                continue
            a = A*pow(2, i)
            b = B*pow(2, j)
            c = C*pow(2, k)
            if a < b and b < c:
                print("Yes")
                exit(0)
print("No")


Measured memory_bytes: 76828
#include<stdio.h>
int main(void)
{
	int a,b;
	scanf("%d %d",&a,&b);
	if(a<b)
	{
		printf("a < b\n");
	}
	else if(a>b)
	{
		printf("a > b\n");
	}
		else if(a==b)
		{
			printf("a == b\n");
		}
	return 0;
}

Measured memory_bytes: 580
n=int(input())
a_b_c_list=[list(map(int,input().split())) for _ in range(n)]

# dp用の空行列（[a,b,c]×[0～n]の行列）
dp = [[0 for i in range(3)] for j in range(n+1)]

# 「1番荷物(i=0)」......「n番荷物(i=n-1)」から何番目までを使うかの場合分け
for i in range(n):
#     for j in range(3):
    dp[i+1][0] = max(dp[i][1],dp[i][2])+a_b_c_list[i][0]
    dp[i+1][1] = max(dp[i][0],dp[i][2])+a_b_c_list[i][1]
    dp[i+1][2] = max(dp[i][0],dp[i][1])+a_b_c_list[i][2]
    
print(max(dp[n]))

Measured memory_bytes: 47388
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


int main(){
	int N = 200000;
	int start;
	int end;
	char S[N];

	scanf("%s",S);

	for(int i = 0; i < strlen(S); i++){
		if(S[i] == 'A'){
			start = i;
			break;
		}
	}

	for (int j = strlen(S); j > 0; j--){
		if(S[j] == 'Z'){
			end = j;
			break;
		}
	}

	printf("%d\n",end - start + 1);
	

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef long long ll;
typedef long double ld;

int gcd(int a, int b)
{
	if (a % b == 0)
		return b;
	else
		return (gcd(b, a % b));
}

int  main()
{
	long n,x; cin >> n >> x;
	vector <long> a(n+1);
	rep(i, n)
		cin >> a[i];
	a[n] = x;
	sort(a.begin(), a.end());
	long ans = abs(a[1] - a[0]);

	for(long i = 0; i < n; i++)
	{
		ans = gcd(ans, abs(a[i] - a[i+1]));
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
  int a,d,i,j;
  int c=0;
  int b=0;
  int e=0;
  int f=0;
  int g=0;
  cin>>a;
  vector<int> vec(a);
  while(i<a){
  cin>>vec.at(i);
    c=c+vec.at(i);
    i++;
  }
   d=c/a;
  while(j<a){
    b+=(vec.at(j)-d)*(vec.at(j)-d);
    e+=(vec.at(j)-d+1)*(vec.at(j)-d+1);
    f+=(vec.at(j)-d-1)*(vec.at(j)-d-1);
    j++;
  }
  
  cout<<min({b,e,f,})<<endl;
}
    
  


Measured memory_bytes: 3640
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
#define all(n) begin(n), end(n)
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
    int n,q;
    cin>>n>>q;
    atcoder::dsu uf(n);
    for (size_t i = 0; i < q; i++)
    {
        int t,u,v;
        cin>>t>>u>>v;
        if(t)
        {
            cout<<uf.same(u,v)<<"\n";
        }
        else
        {
            uf.merge(u,v);
        }
        
    }
    
    return 0;
}

Measured memory_bytes: 3976
#include <iostream>
using namespace std;
int main()
{
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	if (A*B > C*D)
		cout << A*B << endl;
	else if (A*B < C*D)
		cout << C*D << endl;
	else if (A*B == C*D)
		cout << A*B << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)

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

	cout << ((A*B >= C * D) ? A * B : C * D) << endl;

	return 0;
}

Measured memory_bytes: 256
// Vicfred
// https://atcoder.jp/contests/abc045/tasks/abc045_b
import std.array;
import std.stdio;
import std.string;
import std.range.primitives;

void main() {
    string a = readln.strip;
    string b = readln.strip;
    string c = readln.strip;

    char[] A;
    foreach(ch; a)
        A ~= ch;

    char[] B;
    foreach(ch; b)
        B ~= ch;

    char[] C;
    foreach(ch; c)
        C ~= ch;

    char[][char] deck;
    deck['a'] = A;
    deck['b'] = B;
    deck['c'] = C;

    char current = 'a';
    while(deck[current].length > 0) {
        char temp = deck[current][0];
        deck[current].popFront;
        current = temp;
    }

    if(current == 'a')
        "A".writeln;
    if(current == 'b')
        "B".writeln;
    if(current == 'c')
        "C".writeln;
}



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

const int N = 300010;

typedef long long LL;

set<int> A, B, C; int X[N];

int main() {
    int n, L; scanf("%d%d", &n, &L); LL res = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &X[i]);
    for (int i = 1; i <= n; i++) {
        int x = X[i], t; scanf("%d", &t), res += t / (2 * L) * (2 * L), t %= 2 * L;
        int t1 = x * 2 >= t, t2 = (L - x) * 2 >= t;
        if ((i == n && t2) || !t) { res -= 2 * L; continue; }
        if (t1 && t2) C.insert(x);
        else if (t1) A.insert(-x);
        else if (t2) B.insert(x);
    }
    res += (LL)(n + 1) * 2 * L;
    for (auto t : B) if (C.size() && *C.begin() < t) C.erase(C.begin()), res -= 2 * L;
    for (auto t : A) if (C.size() && *C.rbegin() > -t) C.erase(*C.rbegin()), res -= 2 * L;
    res -= (LL)(C.size() / 2) * 2 * L;
    printf("%lld\n", res);
}

Measured memory_bytes: 19000
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>
#define int long long int
#define mod(x) ((x % MOD) + MOD) % MOD
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);--i)

#define ALL(a) (a).begin(),(a).end()
#define SIZE(a) (int)((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

using namespace std;

typedef pair<int,int> P;
struct edge {
  int to, cap, rev;
};

const int INF = 1e18;
const int MOD = 1e9+7;

template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " ";
  }
  return s;
}

void add_edge(vector< vector<edge> >& G, int from, int to, int cap) {
  G[from].push_back((edge){ to, cap, SIZE(G[to])   });
  G[to].push_back((edge){ from, 0, SIZE(G[from])-1 });
}

int dfs(vector< vector<edge> >& G, vector<bool>& used, int v, int t, int flow)
{
  if (v == t) {
    return flow;
  }
  used[v] = true;

  rep(i, 0, SIZE(G[v])) {
    edge& e = G[v][i];
    if (used[e.to] || e.cap == 0) {
      continue;
    }
    int d = dfs(G, used, e.to, t, min(e.cap, flow));
    if (d > 0) {
      e.cap -= d;
      G[e.to][e.rev].cap += d;
      return d;
    }
  }

  return 0;
}

int max_flow(vector< vector<edge> >& G, int s, int t)
{
  int flow = 0;
  vector<bool> used(SIZE(G));
  for (;;) {
    fill(ALL(used), false);
    int f = dfs(G, used, s, t, INF);
    if (f==0) {
      return flow;
    }
    flow += f;
  }
}


signed main()
{
  int N; cin >> N;
  vector< vector<edge> > G(N+2, vector<edge>());

  int sum = 0;
  rep(i, 0, N) {
    int a; cin >> a;
    if (a < 0) {
      add_edge(G, 0, i+1, -a);
    } else {
      add_edge(G, i+1, N+1, a);
      sum += a;
    }
  }

  rep(i, 1, N+1) {
    for(int j=2; i*j <= N; ++j) {
      add_edge(G, i, i*j, INF);
    }
  }

  cout << sum - max_flow(G, 0, N+1) << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String [] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    if(s == null) System.out.println("");
    else{
     	char c = s.charAt(s.length()-1);
    	String str;
		if(c == '2' || c == '4' || c == '5' || c == '7' || c == '9') str = "hon";
    	else if(c == '0' ||c == '1' || c == '6' || c =='8') str = "pon";
    	else str = "bon";
		System.out.println(str);
    }
  }
}


Measured memory_bytes: 26968
import Data.List

ans l =
  let w = sum $ take 3 $ reverse $ sort $ take 10 l
      k = sum $ take 3 $ reverse $ sort $ drop 10 l
  in
    [w,k]

main = do
  c <- getContents
  let i = map read $ lines c :: [Int]
      o = ans i
  putStrLn $ unwords $ map show o

Measured memory_bytes: 3712