akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define repp(i,n) for(int (i) = 1; (i) <= (n); ++(i))
#define popcnt __builtin_popcount
#define all(v) v.begin(),v.end()
#define _Pi 3.1415926535
#define _MOD = 1e9+7;
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b; return true;} return false;}
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b; return true;} return false;}
template<class T> T gcd(T a, T b){return b?GCD(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/GCD(a,b);}

int main(){
    int n; cin >> n;
    vint a(n), b(n);
    rep(i,n) cin >> a[i] >> b[i];
    vector<pint> p(n);
    rep(i,n) p[i] = make_pair(b[i],a[i]);

    sort(all(p));
    int time = 0;
    rep(i,n){
        time += p[i].second;
        if(time <= p[i].first) continue;
        else{
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3328
#include <climits>
#include <iostream>

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

using namespace std;
using ll = long long;

const int M = 1e9 + 7;

const int I_MAX = 5001;
const int J_MAX = 5002;

int dp[I_MAX * J_MAX];


int solve(int n, string s) {

    ll m;
    int o_i, o_n;
    int dp_i0, dp_ij;
    ll ans;
    int r;

    fill(dp, dp + sizeof(dp) / sizeof(dp[0]), 0);
    dp[0] = 1;
    rep (i, 0, n) {
        o_i = J_MAX * i;
        dp_i0 = dp[o_i];
        o_n = o_i + J_MAX;
        dp[o_n] = dp_i0;
        dp[o_n + 1] = dp_i0 * 2 % M;
        rep (j, 1, n + 1) {
            dp_ij = dp[o_i + j];
            dp[o_n + j - 1] = (dp[o_n + j - 1] + dp_ij) % M;
            dp[o_n + j + 1] = (dp[o_n + j + 1] + dp_ij * 2) % M;
        }
    }

    m = s.length();
    ans = dp[J_MAX * n + m];
    r = 5e8 + 4;
    rep (i, 0, m) {
        ans *= r;
        ans %= M;
    }

    return (int)ans;
}


int main(int argc, const char * argv[]) {
    int n;
    string s;

    cin >> n;
    cin >> s;

    cout << solve(n, s) << endl;

    return 0;
}


Measured memory_bytes: 98048
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int s = Integer.parseInt(in.readLine());
    int[] ary = new int[1000000];
    boolean roopFlg = false;
    for(int i=0; ; i++) {
      ary[i] = s;
      if(s%2==0)
        s=s/2;
      else
        s=3*s+1;
      for(int j=0; j<i; j++) {
        if(ary[i]==ary[j]) {
          System.out.println(i+1);
          roopFlg = true;
          break;
        }
      }
      if(roopFlg == true)
        break;
    }
  }
}

Measured memory_bytes: 36188
#include <math.h>
    #include <iostream>
    #include<string>
    #include <algorithm>
    #include <bits/stdc++.h>
    #include <vector>
    #include <stdlib.h>
    using namespace std;
     
    int main()
    {
    int N=0;cin >> N;
    long long ans=0;
    vector<long long> a(3*N);
    for(int i=0;i<3*N;i++){cin >> a.at(i);}
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    for(int i=1;i<2*N;i+=2){ans+=a.at(i);}
    cout << ans;
    }

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
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;}
//自作関数
template<class T> ll llpow(T x,T n){ll ans=1;while(n--){ans*=x;}return ans;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
int te(char x){
    if(x=='r'){
        return 0;
    }
    else if(x=='s'){
        return 1;
    }
    else{
        return 2;
    }
}
long long INF = 1LL<<60;
int main(){
    ll n,k;
    int r,s,p;
    string t;
    cin>>n>>k>>r>>s>>p;
    cin>>t;
    int point[3][3]={0,0,p,r,0,0,0,s,0};
    bool win[n]={false};
    ll ans =0;
    rep(i,n){
        if(i<k){
            ans+=max({point[te(t.at(i))][0],point[te(t.at(i))][1],point[te(t.at(i))][2]});
            win[i]=true;
        }
        else{
            if((t.at(i-k)==t.at(i))&&(win[i-k]==true)){
                ans+=0;
                win[i]=false;
            }
            else{
            ans+=max({point[te(t.at(i))][0],point[te(t.at(i))][1],point[te(t.at(i))][2]});
            win[i]=true;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;
long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }
 
int main(){
    ll N, M;
    cin >> N >> M;
    vector<vector<ll>> ab(N);
    rep(i, M){
        int a, b;
        cin >> a >> b;
        ab[a-1].push_back(b-1);
    }
    for(auto aaa: ab[0]){
        for(auto bbb: ab[aaa]){
            if(bbb==N-1){
                cout << "POSSIBLE" << endl;
                return 0;
            }
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}

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

using namespace std;
const int MAXN = 3e5+5;
long long arr[MAXN];
long long dp[MAXN];
long long suff[MAXN];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=n;i>=0;i--){
        suff[i] = suff[i+1]+arr[i];
    }
    if(arr[0] == 0){
        dp[0] = 1;
    }else if(arr[0] == 1){
        if(n==0){
            cout<<1<<endl;
            return 0;
        }
        cout<<-1<<endl;
        return 0;
    }else{
        cout<<-1<<endl;
        return 0;
    }
    
    for(int i=1;i<=n;i++){
        dp[i] = min(1LL*2*(dp[i-1]-arr[i-1]),suff[i]);
       // cout<<dp[i]<<endl;
        if(dp[i]<arr[i]){
            cout<<-1<<endl;
            return 0;
        }
    }
    long long ans = 0;
    for(int i=0;i<=n;i++){
        ans+=dp[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 5952
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
N = 0
X, Y, H = [], [], []


def set_inputs():
    global N, X, Y, H
    N = get_int()
    X, Y, H = get_data(N, [int, int, int])
    return


def answer(cx, cy):
    x, y, h = next(itertools.dropwhile(
        lambda v: v[2] == 0,
        zip(X, Y, H)
    ))
    ch = h + abs(x - cx) + abs(y - cy)
    for x, y, h in zip(X, Y, H):
        if max(ch - abs(x - cx) - abs(y - cy), 0) != h:
            return False
    print(cx, cy, ch)
    return True


def main():
    setrecursionlimit(100000)
    set_inputs()
    for cx in range(0, 101):
        for cy in range(0, 101):
            if answer(cx, cy):
                return
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()


Measured memory_bytes: 45660
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define cyes cout<<"YES"<<endl
#define cno cout<<"NO"<<endl
#define sp <<" "<<
#define cst(x) cout<<fixed<<setprecision(x)
#define pi 3.14159265359
#define mod 1000000007
using namespace std;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using que_a = priority_queue<int, vector<int>, greater<int> >;
using que_d = priority_queue<int>;
using pint = pair<int,int>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int n; 
vector<vector<vector<ld>>> dp(305,vector<vector<ld>>(305,vector<ld>(305,-1.0)));

ld rec(int one,int two,int three){

    if(one == 0 && two == 0 && three == 0) return 0.0;
    if(dp.at(one).at(two).at(three) >= 0) return dp.at(one).at(two).at(three);

    ld res = 0.0;
    if(one > 0) res += rec(one-1,two,three)*one;
    if(two > 0) res += rec(one+1,two-1,three)*two;
    if(three > 0) res += rec(one,two+1,three-1)*three;
    res += n;
    res /= (one + two + three);

    return dp.at(one).at(two).at(three) = res;
}

int main(){

    cin >> n;
    vector<int> ti(3,0);
    rep(i,n){
        int now; cin >> now;
        now--;
        ti.at(now)++;
    }

    cst(14) << rec(ti.at(0),ti.at(1),ti.at(2)) << endl;

    return 0;   

}


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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9

using namespace std;
typedef long long int lli;
typedef long long ll;

int n,q;
vector<vector<int>> tree(200000, vector<int>());

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

    if(x < 1200) cout << "ABC" << endl;
    else cout << "ARC" << endl;
}


Measured memory_bytes: 4992
/*
    飲んだ魔剤で家が建つ。
    created at: 2020-05-01 22:58:01
*/

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()
#define rev(x) greater<x>()
#define MOD 1000000007
#define INF 1000000000

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

LL modpower(LL n, LL m, LL mod)
{
    if (m == 0) {
        return 1;
    } else if (m % 2 == 0) {
        LL p = modpower(n, m/2, mod);
        return p*p % mod;
    } else {
        return n*modpower(n, m-1, mod) % mod;
    }
}

LL modinv(LL n, LL mod)
{
    return modpower(n, mod-2, mod);
}

LL modcombination(LL n, LL r, LL mod)
{
    LL ret = 1;

    for (int i = 0; i < r; i++) {
        ret *= (n-i);
        ret %= mod;
        ret *= modinv(i+1, mod);
        ret % mod;
    }

    return ret % mod;
}

int gcd(int k, int l)
{
    if (l > 0) return gcd(l, k%l);
    else return k;
}

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n) {
        for (int i = 0; i < n; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main()
{
    int h, w;
    cin >> h >> w;
    string str[h];
    for (int i = 0; i < h; i++)
        cin >> str[i];

    string hash = "";
    for (int i = 0; i < w+2; i++)
        hash += '#';

    cout << hash << endl;
    for (int i = 0; i < h; i++) {
        cout << '#' << str[i] << '#' << endl;
    }
    cout << hash << endl;

    return 0;
}


Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.List (mapAccumL, sort)

main :: IO ()
main = do
  (n : d : a : _) <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    walk :: Int -> Int -> [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
    {-
    walk _ _ [] _ = []
    walk l c ((x, h) : xhs') yks = (x, k') : walk (succ l') (c' + k') xhs' yks'
      where
        (s, t) = splitAt l yks
        (u, v) = span ((< x - 2 * d) . fst) s
        (l', c') = (,) <$> flip subtract l . length <*> flip subtract c . sum . map snd $ u
        k' = (max 0 (h - c' * a) + a - 1) `div` a
        yks' = v ++ t
    -}
    
    walk _ _ [] _ = []
    walk l c ((x, h) : xhs') yks = (x, k') : walk (succ (l - l')) ((c - c') + k') xhs' yks'
      where
        v = take l yks
        u = takeWhile ((< x - 2 * d) . fst) v
        (l', c') = (,) <$> length <*> sum . map snd $ u
        k' = (max 0 (h - (c - c') * a) + a - 1) `div` a
        yks' = drop l' yks
    
    {-
    walk = flip $ mapAccumL step . (,) (0, 0)
      where
        step ((l, c), yks) (x, h) = (((l', c'), yks'), (x, k'))
          where
            (s, t) = splitAt l yks
    -}
  xhs <- sequence . replicate n $ unsafeListToTuple . map unsafeTextToInt . T.words <$> T.getLine :: IO [(Int, Int)]
  print . sum . map snd . fix . walk 0 0 . sort $ xhs

fix :: (a -> a) -> a
fix f = x
  where
    x = f x

unsafeListToTuple :: [Int] -> (Int, Int)
unsafeListToTuple (x : y : _) = (x, y)

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 119164
import java.util.*;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    String str = sc.next();
    char c[] = str.toCharArray();
    boolean t = true;

    for (int i = 0 ; i < 3 ; i++ ) {
      if (c[i] == '7') {
        t = true;
        break;
      } else {
        t = false;
        continue;
      }
    }

    if (t == false) {
      System.out.println("No");
    } else {
      System.out.println("Yes");
    }

  }
}


Measured memory_bytes: 35628
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int MAX = 510000;
const double pi=acos(-1);

int main(){
  rep(i,MOD){
    double n;
    cin >> n;
    if(n==0)return 0;
    vector<double>s(n);
    double sum =0;
    rep(j,n){
      cin >> s[j];
      sum+=s[j];
    }
    sum/=n;
    double ans=0;
    rep(j,n){
      ans+=pow(s[j]-sum,2);
    }
    ans/=n;
    ans=sqrt(ans);
    cout << fixed << setprecision(10) << ans << endl;
  }
}



Measured memory_bytes: 3292
#include <iostream>
using namespace std;
 
int main() {
	int A, B;
  	cin >> A >> B;
	int a = (A + 11) % 13, b = (B + 11) % 13;
	if (a > b) cout << "Alice" << endl;
	if (a < b) cout << "Bob" << endl;
	if (a == b) cout << "Draw" << endl;
}

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

int main() {
  using pp=tuple<string,int,int>;
  int N,i;
  cin>>N;
  vector<pp> a(N);
  for(i=0;i<N;i++){
    cin>>get<0>(a[i])>>get<1>(a[i]);
    get<1>(a[i])=100-get<1>(a[i]);
    get<2>(a[i])=i+1;
  }
  sort(a.begin(),a.end());
  for(i=0;i<N;i++)cout<<get<2>(a[i])<<endl;
}

Measured memory_bytes: 256
#define _DEBUG 1
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
using namespace std;

using ll = long long;


#ifdef _DEBUG
#define dump(x) cerr << #x << "=" << x << endl
#define dump2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define dump3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define check(s) cerr << s << endl
#else
#define dump(x)
#define dump2(x, y)
#define dump3(x, y, z)
#define check(s)
#endif

#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase( unique(v.begin(), v.end()), v.end() );


void solve(ll x, ll a, ll b){
  if (abs(x - a) > abs(x -b)) {
    cout << "B" << endl;
  } else {
    cout << "A" << endl;
  }
}

int main(){
    ll x;
  scanf("%lld",&x);
  ll a;
  scanf("%lld",&a);
  ll b;
  scanf("%lld",&b);
    solve(x, a, b);
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
D - Lazy Faith
https://atcoder.jp/contests/abc119/tasks/abc119_d

"""
import sys
from bisect import bisect_left, bisect_right

def solve(x):
    i = bisect_right(shrines, x)
    ds = x - shrines[i-1]
    j = bisect_right(temples, x)
    dt = x - temples[j-1]
    ans1 = max(ds, dt)

    i = bisect_left(shrines, x)
    ds = shrines[i] - x
    j = bisect_left(temples, x)
    dt = temples[j] - x
    ans2 = max(ds, dt)

    i = bisect_left(shrines, x)
    ds = shrines[i] - x
    j = bisect_right(temples, x)
    dt = x - temples[j-1]
    ans3 = min(ds, dt) * 2 + max(ds, dt)

    i = bisect_right(shrines, x)
    ds = x - shrines[i-1]
    j = bisect_left(temples, x)
    dt = temples[j] - x
    ans4 = min(ds, dt) * 2 + max(ds, dt)

    return min(ans1, ans2, ans3, ans4)


shrines = None
temples = None

def main(args):
    global shrines, temples
    A, B, Q = map(int, input().split())
    shrines = sorted([int(input()) for _ in range(A)] + [float('-inf'), float('inf')])
    temples = sorted([int(input()) for _ in range(B)] + [float('-inf'), float('inf')])
    for _ in range(Q):
        x = int(input())
        ans = solve(x)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 12560
#include<bits/stdc++.h>
#define ll long long
#define dl double
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define mod 1e9+7
#define P(a,b) pair<a,b>
#define CIN(V,s,n) for(int i=s;i<n;i++){cin >> V[i];}
#define COUT(V,s,n) for(int i=s;i<n;i++){cout <<  V[i] << " ";}

using namespace std;
bool sortBylen(string &a,string &b)
{
    if(a.size()>b.size())
        return true;
    else if(a.size()==b.size())
    {
        if(a>b)
        {
            return true;
        }
        else
            false;
    }
    else
        return false;
}
int main()
{
ll t=1;
//cin >> t;
while(t--)
{
    ll n,i,j,k=2,l,m;
    cin >> n;
    vector<ll> dp(n+1,1e9),h(n+1);
    CIN(h,1,n+1);
    dp[0]=0;
    dp[1]=0;
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=k;j++)
        {
            if(i-j>0)
            {
                dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
            }
        }
    }

    cout << dp[n] << endl;


}

	return 0;
}


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

using namespace std;

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

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back


int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        
        vi in;
        rep(i,n){
            int a;
            cin>>a;
            in.pb(a);
        }
        
        sort(all(in));
        
        vi tmp;
        tmp.clear();
        
        vector<string> ans;
        
        rep(i,in.size()){
            if(i+1<in.size() && in[i]+1==in[i+1]){
                tmp.pb(in[i]);
            }
            else{
                if(tmp.size()==0){
                    stringstream ss;
                    ss<<in[i];
                    ans.pb(ss.str());
                }
                else{
                    stringstream ss;
                    ss<<tmp[0];
                    ss<<"-";
                    ss<<in[i];
                    ans.pb(ss.str());
                    tmp.clear();
                }
            }
        }
        rep(i,ans.size()){
            cout<<ans[i];
            if(i<ans.size()-1)cout<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<double> v(n, 0.0);
    rep(i, n) cin >> v[i];
    sort(ALL(v));
    while (v.size() != 1)
    {
        vector<double> next;
        rep(i, 2, v.size())
        {
            next.push_back(v[i]);
        }
        next.push_back((v[0] + v[1]) / 2);
        v = next;
        sort(ALL(v));
    }
    printf("%f\n", v[0]);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n ,a[100001];
map<int ,int > m;
int main()
{

   cin >> n ;
    for (int i = 1 ; i <= n ; i++)cin >> a[i] , m[a[i]] = i ;
    for (auto i : m )cout << i.second <<" " ;
    return 0;
}


Measured memory_bytes: 5888
import sys
import heapq
import itertools

INF = 10**18

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def dijkstra(N, s0, edge):

    d = [INF] * N
    pre_v = [-1] * N
    used = [False] * N
    edgelist = [(0, s0, -1)]
    heapq.heapify(edgelist)

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue

        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        pre_v[v] = minedge[2]

        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, (e[0] + d[v], e[1], v))
    return d, pre_v


def main():

    N, M, R = in_nn()
    r = in_nl()
    r = [t - 1 for t in r]
    edge = [[] for _ in range(N)]

    for i in range(M):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    dis = [[-1] * N for _ in range(N)]
    for i in range(R):
        s = r[i]
        d, pre_v = dijkstra(N, s, edge)

        for j in range(R):
            e = r[j]
            dis[s][e] = d[e]

        for j in range(R):
            if i == j:
                continue

            e = r[j]
            tr = set(r) - {e} - {s}
            while e != -1:
                t = pre_v[e]
                if t in tr:
                    dis[s][e] = -1
                    break
                else:
                    e = t

    perm = itertools.permutations(r, R)

    ans = INF
    for per in perm:

        td = 0
        for i in range(R - 1):
            s, e = per[i], per[i + 1]
            if dis[s][e] == -1:
                break
            else:
                td += dis[s][e]
        else:
            ans = min(ans, td)

    # print(dis)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 15312
function Main(input) {
  input = input.split('\n')
  var N = parseInt(input[0])
  var p = input[1].split(' ').map(str => parseInt(str))
  var counter = 0

  for (var i = 0; i < N; i++) {
    if (p[i] !== i + 1) {
      counter++
    }
  }

  if (counter <= 2) {
    console.log('YES')
  } else {
    console.log('NO')
  }
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'))



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

int main(){
  ll n;
  cin >> n;
  n--;
  ll a = 26;
  int b = 1;
  while(true) {
    if(n - a < 0) break;
    n -= a;
    a *= 26;
    b++;
  }
  string s = "";
  rep(i,b) {
    a /= 26;
    ll d = n / a;
    n -= (d*a);
    s += (char)('a'+d); 
  }
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3608
def solve():
    N, M = [int(x) for x in input().split()]

    from_1 = set()
    to_N = set()
    for i in range(M):
        u, v = [int(x) for x in input().split()]

        if u == 1:
            from_1.add(v)

        if v == N:
            to_N.add(u)

    ss = from_1.intersection(to_N)
    return len(ss) != 0


def main():
    ans = solve()
    if ans:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Measured memory_bytes: 19012
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool check(vector<ll>& W, ll k, ll p) {
    int n = W.size();
    ll sum = 0, truck = 1;
    for ( int i = 0; i < n; i++ ) {
        if ( W[i] > p ) return false;
        if ( sum + W[i] <= p ) {
            sum += W[i];
        } else {
            truck++;
            sum = W[i];
        }
        if ( truck > k ) return false;
    }
    return true;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<ll> W(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> W[i];
    }

    ll p_min = 0, p_max = 1000000000LL, p;
    while (p_max - p_min > 1) {
        p = ( p_max + p_min ) / 2;
        if ( check(W, K, p) ) p_max = p;
        else p_min = p;
    }

    cout << (p_min + 1) << '\n';
    return 0;
}


Measured memory_bytes: 3540
// スタックサイズ: 100MB

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
using namespace std;

typedef int64_t ll;
const ll INF = 1000000000000000000;
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define vll vector<ll>
#define all(v) (v).begin(), (v).end()



int main() {
	
	ll N, M;
	cin >> N >> M;
	vector<pair<ll, ll>> ab(M);
	rep(i, M) {
		ll a, b;
		cin >> a >> b;
		ab[i] = pair<ll, ll>(a, b);
	}

	ll ans = 0;
	auto it = ab.begin();
	while (it != ab.end()) {
		sort(it, ab.end(), [](pair<ll, ll>x, pair<ll, ll>y) {
			return x.second < y.second;
		});

		ll base = it->second;
		sort(it, ab.end(), [](pair<ll, ll>x, pair<ll, ll>y) {
			return x.first < y.first;
		});
		it = lower_bound(it, ab.end(), base, [](pair<ll, ll>x, ll y) {
			return x.first < y;
		});
		++ans;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
// https://atcoder.jp/contests/abc165/tasks/abc165_c
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define is_in(i, s) (s.find(i) != s.end())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> P;

#define MAX_N 11
int N,M,Q;
struct EDGE{int a,c,d;};
vector<EDGE> e[MAX_N];


int calc(vector<int> history){
	int i = history.size()-1;
	if(i==N-1)return 0;
	int smax = 0;
	for(int j=history[i];j<=M;j++){
		int score=0;
		rep(k,e[i+1].size()){
			if(j-history[e[i+1][k].a]==e[i+1][k].c){
				score += e[i+1][k].d;
			}
		}
		vector<int> h2(i+2);
		rep(k,i+1)h2[k]=history[k];
		h2[i+1] = j;
		smax=max(smax,calc(h2)+score);
	}
	return smax;
}

int main() {
	cin >> N >> M >> Q;
	rep(i,Q){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		a--;b--;
		e[b].push_back(EDGE{a,c,d});
	}
	

	vector<int> h(1);
	h[0]=1;
	cout << calc(h) << endl;

    return 0;
}



Measured memory_bytes: 3544
/**
 * File    : D.cpp
 * Author  : Kazune Takahashi
 * Created : 2018-7-1 20:39:17
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <random> // random_device rd; mt19937 mt(rd());
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

// const int C = 1e6+10;
const ll infty = 1000000000000007;

int N;
ll A[200010];
ll sum = 0;
ll imos[200010];

int index(ll sum)
{
  int lb = 0;
  int ub = N - 1;
  if (sum < imos[lb])
  {
    return lb;
  }
  while (ub - lb > 1)
  {
    int t = (ub + lb) / 2;
    if (sum < imos[t])
    {
      ub = t;
    }
    else
    {
      lb = t;
    }
  }
  return lb;
}

int main()
{
  cin >> N;
  for (auto i = 0; i < N; i++)
  {
    cin >> A[i];
    sum += A[i];
  }
  fill(imos, imos + 200010, 0);
  imos[0] = A[0];
  for (auto i = 1; i < N; i++)
  {
    imos[i] = imos[i - 1] + A[i];
  }
  ll ans = infty;
  for (auto s = 1; s < N - 2; s++)
  {
    ll PQ = imos[s];
    ll RS = sum - imos[s];
    int ind = index(PQ / 2);
    for (auto k = ind - 2; k <= ind + 2; k++)
    {
      if (0 <= k && k < s)
      {
        ll P = imos[k];
        ll Q = PQ - P;
        ll ind2 = index(PQ + RS / 2);
        for (auto t = ind2 - 2; t < ind2 + 2; t++)
        {
          if (s < t && t < N - 1)
          {
            // cerr << "k = " << k << ", s = " << s << ", t = " << t << endl;
            ll R = imos[t] - PQ;
            ll S = RS - R;
            ll maxi = max(max(P, Q), max(R, S));
            ll mini = min(min(P, Q), min(R, S));
            ans = min(ans, maxi - mini);
          }
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3328
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string.h>

const int MAXN = 1000000000;
const int MAX_BOUND = 31623;
char isprime[MAX_BOUND];

struct Primes
{
	int arr[MAX_BOUND];
	int size;
}sprimes;

struct PrimeInfo
{
	int v;
	int cnt;
};
struct PrimeArr
{
	PrimeInfo primes[MAX_BOUND];
	int size;
};
PrimeArr arr;

bool is_prime(const int n) {
	int b = (int)sqrt(n) + 1;
	for (int i = 2; i < b; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

void init() {
	memset(isprime, -1, sizeof(isprime));
	memset(&arr, 0, sizeof(arr));
	sprimes.size = 0;
	for (int i = 2; i < MAX_BOUND; i++) {
		if (isprime[i]) {
			sprimes.arr[sprimes.size++] = i;
			for (int j = i * i; j < MAX_BOUND; j += i) {
				isprime[j] = 0;
			}
		}
	}
}

void getrs(const int n) {
	if (is_prime(n)) {
		printf("%d\n", n - 1);
		return;
	}
	//
	int r = n;
	int b = (int)sqrt(n) + 1;
	for (int i = 0; i < sprimes.size; i++) {
		if (sprimes.arr[i] > r || r == 1) { break; }
		if (r % sprimes.arr[i] == 0) {
			arr.primes[arr.size].v = sprimes.arr[i];
			while (r % sprimes.arr[i] == 0) {
				//
				r /= sprimes.arr[i];
			}
			arr.size++;
		}
	}
	if (r != 1) {
		arr.primes[arr.size++].v = r;
	}
	int left = n, right = 1;
	for (int i = 0; i < arr.size; i++) {
		left /= arr.primes[i].v;
		right *= (arr.primes[i].v - 1);
	}
	printf("%d\n", left * right);
}


int main() {
	int n;
	scanf("%d", &n);
	init();
	getrs(n);
	return 0;
}


Measured memory_bytes: 3048
N = int(input())
A = list(map(int, input().split()))

sumA, mod, ans = [0], 10 ** 9 + 7, 0
for a in A:
    sumA.append((sumA[-1] + a) % mod)

for i in range(1, N):
    ans = (ans + (sumA[N - i] * A[N - i]) % mod) % mod
print(ans)


Measured memory_bytes: 102176
n = int(input())
arr = []
for i in range(n):
	x, l = map(int, input().split())
	r = x+l
	l = x-l
	arr += [[l, r]]
arr.sort()
# print(arr)
ma = -888888888
count = 0
for i in range(n):
	if arr[i][0] < ma:
		count += 1
		ma = min(ma, arr[i][1])
	else:
		ma = arr[i][1]
print(n-count)

Measured memory_bytes: 20076
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = 1e9;
const int MOD = 1000000007;

 
int main() {
  ll n,w;
  cin >> n >> w;
  vector<deque<ll>> mp(4,deque<ll>());
  ll w_ = 0;
  rep(i,n){
    int a,b;
    cin >> a >> b;
    if(i==0) {
      w_ = a;
      mp.at(0).emplace_back(b);
    }else{
      mp.at(a-w_).emplace_back(b);
    }
  }
  
  rep(i,4){
    sort(mp[i].begin(),mp[i].end(),greater<ll>());
  }
  
  rep(i,4){
    rep(j,(int)(mp[i].size())-1){
      mp[i][j+1] += mp[i][j];
    }
  }
  
  rep(i,4){
    mp[i].push_front(0);
  }
  
  /*rep(i,4){
    rep(j,(int)(mp[i].size())){
      cout << mp[i][j] << " ";
    }
    cout << endl;
  }*/
  
  ll ans = 0;
  rep(i,(int)(mp[0].size())){
    rep(j,(int)(mp[1].size())){
      rep(k,(int)(mp[2].size())){
        rep(l,(int)(mp[3].size())){
          if(i*w_+j*(w_+1)+k*(w_+2)+l*(w_+3) > w) continue;
          ans = max(ans,mp[0][i]+mp[1][j]+mp[2][k]+mp[3][l]);
        }
      }
    }
  }

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





Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static int number;
    public static int table[];
    public static boolean check[];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        number = scan.nextInt();
        table = new int[number];
        check = new boolean[2000 + 1];
        for (int i = 0; i < number; i++){
            table[i] = scan.nextInt();
        }
        solve(0, 0);
        int q = scan.nextInt();
        for (int i = 0; i < q; i++){
            int m = scan.nextInt();
            if(check[m]){
                System.out.println("yes");
            } else {
                System.out.println("no");
            }
        }

        scan.close();
    }

    public static void solve(int i, int m) {
        if (i == number) {
            check[m] = true;
            return;
        }

        solve(i+1, m);
        if (m + table[i] <= 2000) {
            solve(i+1, m+table[i]);
        }
    }
}


Measured memory_bytes: 26736
S = list(input())
T = list(input())

ans = []


for i in range(len(S)-len(T)+1):
    diff = 0
    for j in range(len(T)):
        if S[i:i+len(T)][j] == T[j]:
            pass
        else:
            diff += 1
    ans.append(diff)
    

print(min(ans))

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

int main() {
  for(int tci = 0; ; tci++) {
    int W; scanf("%d", &W); if(!W) break;
    int N; scanf("%d", &N);
    static int v[10000],w[10000];
    for(int i = 0; i < N; i++) {
      scanf("%d,%d", v+i, w+i);
    }
    static int knap[1001][1001];
    for(int i = 0; i <= N; i++) fill(knap[i], knap[i]+W+1, 0);
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < w[i]; j++) {
        knap[i+1][j] = knap[i][j];
      }
      for(int j = w[i]; j <= W; j++) {
        knap[i+1][j] = max(knap[i][j],knap[i][j-w[i]]+v[i]);
      }
    }
    pair<int,int> mval(0,0);
    for(int j = 0; j <= W; j++) {
      mval = max(mval, make_pair(knap[N][j],-j));
    }
    printf("Case %d:\n%d\n%d\n", tci+1, mval.first, -mval.second);
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define hackcyborg shresth_walia
#define ll long long int
#define ld long double
#define FOR(i,a,b) for (auto i = (a); i != (b); i = (a)<(b)? i+1 : i-1)
#define pb push_back
#define mod 1000000007
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    ll ans=0;
    while(n>0)
    {
        if(n%10==7)
            ans=1;
        n/=10;
    }
    if(ans)
    cout<<"Yes";
    else
        cout<<"No";
}


Measured memory_bytes: 3604
a, b = input().split()
s1 = []
s2 = []
for i in range(int(b)):
    s1.append(a)

for i in range(int(a)):
    s2.append(b)
s1 = "".join(s1)
s2 = "".join(s2)

if s1 > s2:
    print(s2)
else:
    print(s1)


Measured memory_bytes: 2940
use std::collections::HashSet;

fn main() {
    let _ = read::<usize>();
    let hs = read::<String>().chars().collect::<HashSet<_>>();
    let ans = hs.iter().count();
    if ans == 5 { // with space
        println!("Four");
    } else if ans == 4 {
        println!("Three");
    } else {
        println!("???");
    }
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


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

using namespace std;

#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define repr(i, j) for(int i = j; i >= 0; -i)
#define INF (1 << 30)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

int main() {
	string sa, sb, sc;
	char now = 'a';
	cin >> sa >> sb >> sc;
	while(1) {
		//cout << sa << " " << sb << " " << sc << endl;
		if(now == 'a') {
			if(sa.size() == 0) {
				cout << "A" << endl;
				break;
			}
			now = sa[0];
			sa.erase(0, 1);
		}
		else if(now == 'b') {
			if(sb.size() == 0) {
				cout << "B" << endl;
				break;
			}
			now = sb[0];
			sb.erase(0, 1);
		}
		else if(now == 'c') {
			if(sc.size() == 0) {
				cout << "C" << endl;
				break;
			}
			now = sc[0];
			sc.erase(0, 1);
		}
	}
	return 0;
}

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

#define int long long
#define ff first
#define ss second
#define loop(i,k,n) for(int i=k;i<n;++i)
#define rloop(i,n,k) for(int i=n;i>=k;i--)
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpii vector<pair<int,int> >
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define mci map<char,int>  
#define pii pair<int,int>
#define pdd pair<double,double>
#define deb(x) cout<<#x<<" "<<x<<endl;
#define mp make_pair
#define pb push_back
#define mod 1000000007  
#define endl "\n"
#define inf 1e18
#define sp(x,y) fixed<<setprecision(y)<<x

void get_it_done(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
int gcd(int a, int b){ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
void swap(int &a,int &b){
	a^=b;b^=a;a^=b;
}
const int N = 1e5+5;
int dp[N][3];
int n;
int activity[N][3];

int solve(int i,int cnt){
    if(i>=n)
        return 0;
    if(dp[i][cnt]!=-1)
        return dp[i][cnt];
    int ans = 0;
    ans = activity[i][cnt] + max(solve(i+1,(cnt+1)%3),solve(i+1,(cnt+2)%3));
    return dp[i][cnt] = ans;
}

int32_t main(){
	get_it_done();
    int t=1;
    // cin >> t;
    while (t--){
        cin>>n;
        loop(i,0,n) loop(j,0,3) cin>>activity[i][j];
        memset(dp,-1,sizeof(dp));
        // cout<<solve(0,0);
        dp[0][0] = activity[0][0];
        dp[0][1] = activity[0][1];
        dp[0][2] = activity[0][2];
        loop(i,1,n){
            loop(j,0,3){
                dp[i][j] = max(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3])+activity[i][j];
            }
        }
        int ans = max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
        cout<<ans<<endl;

    }
}


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

int main(){
	int x,a,b; cin>>x>>a>>b;
	int c=(x-a)/b;
	cout << x-a-c*b << endl;	
}


Measured memory_bytes: 256
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

a, b = rm()
if a <= b:
  print(a)
else:
  print(a-1)
















Measured memory_bytes: 27168
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
'''
def GI(V,E,DAG=False,index=0):
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[1:])
            bb=(inp[1:])
        g[a].append(b)
        if g[b].append(a)
        h.append(b)
'''

def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
show_flg=True



n=I()

dp=[0]*(1+n)
dp[100:106]=[1]*6
for i in range(1+n):
    for j in range(100,106):
        if i-j>=0:
            dp[i]=max(dp[i],dp[i-j])
print(dp[n])

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

const int maxn = 1000010, P = 998244353;
int n, tot, p[maxn], c[maxn], inv[maxn], mu[maxn], tmp[maxn];

int qp(int x, int y) {
    int z = 1;
    for (; y; y >>= 1, x = 1LL * x * x % P) {
        if (y & 1) z = 1LL * z * x % P;
    }
    return z;
}

void sieve() {
    fill(p, p + maxn, 1), mu[1] = 1;
    for (int i = 2; i < maxn; i++) {
        if (p[i]) p[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * p[j] < maxn; j++) {
            p[i * p[j]] = 0;
            if (i % p[j]) mu[i * p[j]] = -mu[i];
            else { mu[i * p[j]] = 0; break; }
        }
    }
}

int main() {
    scanf("%d", &n), sieve();
    for (int i = 1; i < maxn; i++) {
        inv[i] = qp(i, P - 2);
    }
    int ans = 0;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x), (c[x] += x) %= P, (ans -= x) %= P;
    }
    for (int i = 1; i < maxn; i++) {
        for (int j = i; j < maxn; j += i) {
            (tmp[i] += c[j]) %= P;
        }
        tmp[i] = 1LL * tmp[i] * tmp[i] % P;
    }
    for (int i = 1; i < maxn; i++) {
        for (int j = 1; i * j < maxn; j++) {
            ans = (ans + 1LL * mu[i] * inv[j] % P * tmp[i * j]) % P;
        }
    }
    printf("%d\n", 1LL * qp(2, P - 2) * (ans + P) % P);
    return 0;
}

Measured memory_bytes: 19712
def count_sort(numlist, n):
    C = [0 for i in range(n + 1)]
    B = [0 for i in range(len(numlist))]
    # store times that num has appear
    for num in numlist:
        C[num] += 1
    # cal index
    for i in range(1, n + 1):
        C[i] += C[i - 1]
    for n in range(len(numlist), 0, -1):
        C[numlist[n - 1]] -= 1
        B[C[numlist[n - 1]]] = numlist[n - 1]

    return B

if __name__ == '__main__':
    n = int(input())
    numlist = [int(num) for num in input().split(' ')]
    numlist = count_sort(numlist, max(numlist))
    print(str(numlist).replace(',', '').replace('[', '').replace(']', ''))


Measured memory_bytes: 224228
import sys

def solve():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    A = [int(t) for t in input().split()]

    Ans = 0
    currentTime = A[0]
    for i in range(1, N):
        if A[i] - currentTime < T: Ans += A[i] - currentTime
        else: Ans += T
        currentTime = A[i]
    Ans += T
    print(Ans)
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 25104
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h> // uint64_t

#define BUF_SIZE 30

// size: specify sizeof(str)
int get_str(char *str, int size) {
    if(!fgets(str, size, stdin)) return -1;
    return 0;
}

int get_int(void) {
  int num;
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return 0;
  sscanf(line, "%d", &num);
#else
#error
#endif
  return num;
}

int get_int2(uint64_t *a1, uint64_t *a2) {
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return -1;
  sscanf(line, "%llu %llu", a1, a2);
#else
#error
#endif
  return 0;
}

#define NUM_MAX 100
#define VALUE_MAX (1000*NUM_MAX)

struct product {
    uint64_t w;
    uint64_t v;
};

#define min(a,b) ((a) > (b) ? (b) : (a))

int main(void) {
    uint64_t num, wlimit;
    get_int2(&num, &wlimit);
    static uint64_t dp[NUM_MAX+1][VALUE_MAX+1];
    memset(dp, 0x01, sizeof(uint64_t)*(NUM_MAX+1)*(VALUE_MAX+1));
    dp[0][0] = 0;
    static struct product prod[NUM_MAX+1];
    int i, j;
    for(i = 1; i <= num; i++) {
        get_int2(&prod[i].w, &prod[i].v);
    }

    int vlimit = 0;
    for(i = 1; i <= num; i++) {
        uint64_t w = prod[i].w;
        int v = prod[i].v;
        vlimit += v;
        vlimit = min(vlimit, VALUE_MAX);
        for(j = 0; j <= vlimit; j++) {
            dp[i][j] = dp[i-1][j];
            if(j-v>=0) dp[i][j] = min(dp[i][j], dp[i-1][j-v]+w);
        }
    }
    for(i = VALUE_MAX; i >= 0; i--) {
        if(dp[num][i] <= wlimit) {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <map>
// #include <algorithm>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

template<typename T>
T mod(T a, T b){
    return (a + b) % b;
}

template<typename T>
T gcd(T a, T b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b){
    return a * b / gcd(a,b);
}

// n を素因数分解
map<ll, ll> factor(ll n){
    map<ll, ll> mp;
    for (ll i = 2; i*i <= n; i++) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }

    if (n > 1) {
        mp[n]++;
    }

    return mp;
}

// 文字列に "hoge" が含まれているか
// string str = "hogepiyo";
// if (str.find("hoge") != string::npos) {
//     cout << "文字列が含まれています" << endl;
// }

// char to string
// char c = 'a';
// string str = {c};

void solve(){
    int H, W;
    cin >> H >> W;

    int h,w;
    cin >> h >> w;

    cout << H*W - h*W - w*H + h*w << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 256