akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



struct Edge{
	Edge(int arg_to,ll arg_coin,ll arg_cost){
		to = arg_to;
		coin = arg_coin;
		cost = arg_cost;
	}
	int to;
	ll coin,cost;
};

struct Info{
	Info(int arg_node_id,ll arg_coin,ll arg_sum_dist){
		node_id = arg_node_id;
		coin = arg_coin;
		sum_dist = arg_sum_dist;
	}
	bool operator<(const struct Info &arg) const{

		return sum_dist > arg.sum_dist; //総距離の曹純(PQ)
	}

	int node_id;
	ll coin,sum_dist;
};

int N,M;
ll S;
ll min_dist[55][5005];
ll C[55],D[55];
vector<Edge> G[55];


int main(){

	scanf("%d %d %lld",&N,&M,&S);

	int from,to;
	ll coin,cost;
	ll total = 0;

	for(int i = 0; i < M; i++){

		scanf("%d %d %lld %lld",&from,&to,&coin,&cost);
		from--;
		to--;
		total += coin;

		G[from].push_back(Edge(to,coin,cost));
		G[to].push_back(Edge(from,coin,cost));
	}

	for(int i = 0; i < N; i++){

		scanf("%lld %lld",&C[i],&D[i]);
	}

	for(int i = 0; i < N; i++){
		for(int k = 0; k <= total; k++){

			min_dist[i][k] = HUGE_NUM;
		}
	}

	S = min(S,total);

	priority_queue<Info> Q;
	Q.push(Info(0,S,0));

	while(!Q.empty()){

		if(Q.top().sum_dist > min_dist[Q.top().node_id][Q.top().coin]){

			Q.pop();

		}else{

			for(ll add = 0; ; add++){ //金→銀の枚数

				ll next_coin = Q.top().coin+C[Q.top().node_id]*add;
				if(next_coin > total){

					next_coin = total;
				}
				ll next_dist = Q.top().sum_dist+D[Q.top().node_id]*add;

				for(int i = 0; i < G[Q.top().node_id].size(); i++){

					if(G[Q.top().node_id][i].coin > next_coin)continue;
					int next_node = G[Q.top().node_id][i].to;

					ll work_coin = next_coin-G[Q.top().node_id][i].coin;
					ll work_dist = next_dist+G[Q.top().node_id][i].cost;

					if(min_dist[next_node][work_coin] > work_dist){

						min_dist[next_node][work_coin] = work_dist;
						Q.push(Info(next_node,work_coin,work_dist));
					}
				}


				if(Q.top().coin+C[Q.top().node_id]*add >= total){

					break;
				}
			}

			Q.pop();
		}
	}

	for(int i = 1; i < N; i++){
		ll ans = HUGE_NUM;
		for(ll k = 0; k <= total; k++){

			ans = min(ans,min_dist[i][k]);
		}

		printf("%lld\n",ans);
	}

	return 0;
}


Measured memory_bytes: 53580
import sys
input = sys.stdin.readline

h, w, m = map(int, input().split())
G = [list(map(lambda x:int(x)-1, input().split())) for _ in range(m)]
A = [0]*h
B = [0]*w
for i, j in G:
  A[i] += 1
  B[j] += 1
ans = 0
max_A = max(A)
max_B = max(B)
cnt = A.count(max_A) * B.count(max_B)
for i, j in G:
  if A[i] == max_A and B[j] == max_B:
    cnt -= 1
if cnt == 0:
  print(max_A+max_B-1)
else:
  print(max_A+max_B)

Measured memory_bytes: 123848
import sys

def main():
    r,D,x2k=input().split()

    moGram(r,D,x2k,2010)


def moGram(r, D, x2k, i) :

    if i == 2000 :
        return x2k
    else :
        oldGram = moGram(r, D, x2k, i-1) 
        gram = int(r)*int(oldGram) - int(D)
        print(gram)
        return gram

main()

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

using namespace std;
typedef long long LL;

int a[4];
int k;
bool cmp(int x ,int y)
{
	return x < y;
}
int main()
{
	scanf("%d %d %d",&a[1],&a[2],&a[3]);
	scanf("%d",&k);
	sort(a + 1,a + 1 + 3,cmp);
	for(int i = 1;i <= k;i++)
	{
		a[3] *= 2;
	}
	printf("%d\n",a[1] + a[2] + a[3]);
}

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

using namespace std;
using ll = long long;

// ll N;

bool query(string n) {
    cout << "? " << n << endl;
    char res;
    cin >> res;
    return res == 'Y';

    // bool res = ((stoll(n) <= N) == (n <= to_string(N)));
    // cerr << "NY"[res] << endl;
    // return res;
}

void answer(string n) {
    cout << "! " << n << endl;
}

int main() {
    // cin >> N;

    string ten = "1" + string(10, '0');
    if (query(ten)) {
        // 解は10^k
        ten[0] = '2';
        ten.pop_back();
        while (!ten.empty()) {
            if (!query(ten)) break;
            ten.pop_back();
        }

        if (ten.empty()) {
            answer("1");
        } else {
            ten.push_back('0');
            ten[0] = '1';
            answer(ten);
        }
        return 0;
    }

    ten.pop_back();
    while (!ten.empty()) {
        if (query(ten)) break;
        ten.pop_back();
    }

    //　答えはk桁
    int k = ten.length();
    string ans = "";
    for (int i = 0; i < k - 1; ++i) {
        // 上からi桁目を二分探索
        int ok = 0, ng = 10;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            if (query(ans + char('0' + mid))) {
                ok = mid;
            } else {
                ng = mid;
            }
        }

        ans.push_back(ok + '0');
    }

    // 最後の1桁を求める
    for (int i = 0; i < 10; ++i) {
        // 1桁のときは例外
        if (i == 0 && k == 1) continue;

        if (query(ans + char(i + '0') + '0')) {
            ans.push_back(i + '0');
            break;
        }
    }

    answer(ans);
    return 0;
}


Measured memory_bytes: 596
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
 
int main(){
        queue<long long> que;
        int N;
        cin >> N;
 
        if(N<10){
                cout << N;
                return 0;
        }
 
        for(int i=1; i<=9 ; i++){
                que.push(i);
        }
        int count = 9;
        while(count != N){
                long long number = que.front();
                que.pop();
                vector<int> nexts;
                short last = number%10;
                switch(last){
                        case 0:
                                                   nexts.push_back(0);
                                nexts.push_back(1);
                                break;
                        case 1:
                        case 2:
                        case 3:
                        case 4:
                        case 5:
                        case 6:
                        case 7:
                        case 8:
                                for(int i= last-1;i<= last+1; i++ ){
                                        nexts.push_back(i);
                                }
                                break;
                        case 9:
                                nexts.push_back(8);
                                nexts.push_back(9);
                }
                for(short next: nexts){
                        count++;
                        if(count == N){
                                cout << number*10 + next;
                                break;
                        }
                        que.push(number *10 + next);
                }
        }
}

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

using ll = long long;
#define repi(n) for (int i = 0; i < (n); i++)
#define repj(n) for (int j = 0; j < (n); j++)
#define repk(n) for (int k = 0; j < (n); k++)
#define rep(i, n) for (int i = 0; (i) < (n); i++)
#define repr(i, a, b) for (auto i = (a); i < (b); i++)
#define repv(itr) for (auto&& v : (itr))
#define updatemax(t, v) (t = max((t), (v)))
#define updatemin(t, v) (t = min((t), (v)))
const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
template <typename T>
T minptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i < *re) re = i;
  }
  return re;
}
template <typename T>
T maxptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i > *re) re = i;
  }
  return re;
}
int __vmax(int x) {
  return INT_MAX;
}
double __vmax(double x) {
  return 1e+300;
}
ll __vmax(ll x) {
  return LLONG_MAX;
}
int __vmin(int x) {
  return INT_MIN;
}
double __vmin(double x) {
  return -1e+300;
}
ll __vmin(ll x) {
  return LLONG_MIN;
}
template <typename T>
vector<T> lis(T begin, T end, bool allowequal = false, bool lds = false) {
  using V = typename iterator_traits<T>::value_type;
  int n = end - begin;
  vector<V> a(n, lds ? __vmin(*begin) : __vmax(*begin));
  vector<int> id(n);
  if (lds && allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (lower_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (lds) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (upper_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = upper_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  } else {
    for (int i = 0; i < n; i++) {
      id[i] = lower_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  }
  int m = *maxptr(id.begin(), id.end());
  vector<T> re(m + 1);
  for (int i = n - 1; i >= 0; i--) {
    if (id[i] == m) re[m--] = begin + i;
  }
  return re;
}

bool rec[1000010];
int main() {
  int s;
  cin >> s;
  rec[s] = true;
  repi(1000010) {
    s = s % 2 ? 3 * s + 1 : s / 2;
    if (rec[s]) {
      cout << i + 2 << endl;
      break;
    }
    rec[s] = true;
  }
}


Measured memory_bytes: 256
#include <stdio.h>

#define MAX_OPERANDS 128

int opeStack[MAX_OPERANDS];
int opeSp = 0;

int main(int argc, char* argv[]) {
  int tmp = 0;
  for (;;) {
    int c = getchar();
    if (c == EOF) break;
    if (c == ' ') {
      opeStack[opeSp++] = tmp;
      tmp = 0;
      continue;
    }
    if ('0' <= c && c <= '9') {
      tmp *= 10;
      tmp += c - '0';
      continue;
    }
    if (c == '+') {
      opeStack[opeSp - 2] = opeStack[opeSp - 2] + opeStack[opeSp - 1];
    } else if (c == '-') {
      opeStack[opeSp - 2] = opeStack[opeSp - 2] - opeStack[opeSp - 1];
    } else if (c == '*') {
      opeStack[opeSp - 2] = opeStack[opeSp - 2] * opeStack[opeSp - 1];
    }
    opeSp--;
    getchar();
  }
  printf("%d\n", opeStack[0]);
  return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

// factorial(階乗)の計算
const int N_MAX = pow(10,3)*2;
ll fac[N_MAX+1] = {};
ll inv_fac[N_MAX+1] = {};
ll c_fac(int n=N_MAX) {
  if (fac[n]!=0) return fac[n];
  if (n==0) return fac[n]=1;
  return fac[n] = (c_fac(n-1)*n)%MOD;
}

// inverse(逆元)の計算
ll inv(ll a,ll m=MOD) {
  ll b = m, x = 1, y = 0;
  while (b!=0) {
    ll d = a/b;
    a -= b*d; swap(a, b);
    x -= y*d; swap(x, y);
  }
  return x>=0 ? x : x+m;
}

// combinataionの計算
ll nck(ll n, ll k) { 
  c_fac(n);
  if (n<k) return 0;
  ll nume = fac[n];
  ll deno = ( inv(fac[n-k]) * inv(fac[k]) ) % MOD;
  return ( nume * deno ) % MOD;
}

int main() {
  int N, A, B, C, D; cin >> N >> A >> B >> C >> D;
  c_fac();
  rep(i,N_MAX+1) inv_fac[i] = inv(fac[i]);

  ll dp[(B-A+1)+1][N+1] = {}; dp[0][0] = 1;
  ll count = 0;
  repr(i,A,B+1) {
    rep(j,N+1) dp[i-A+1][j] = dp[i-A][j];
    repr(j,C*i,N+1) {
      ll pfi = 1; rep(k,C) { pfi *= fac[i]; pfi %= MOD; }
      for (int k=C; j-k*i>=0&&k<=D; k++) {
        ll num = dp[i-A][j-k*i];
        num *= fac[N-(j-k*i)]; num %= MOD;
        num *= inv_fac[N-j]; num %= MOD;
        num *= inv(pfi); num %= MOD;
        num *= inv_fac[k]; num %= MOD;
        dp[i-A+1][j] += num; dp[i-A+1][j] %= MOD;
        pfi *= fac[i]; pfi %= MOD;
      }
    }
  }
  // rep(i,B-A+2) debug(dp[i],dp[i]+N+1);
  ll result = dp[B-A+1][N];
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 8064
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

# N = int(sys.stdin.readline())
#
# a = math.factorial(N) % (10 ** 9 + 7)
# print(a)
# # print(pow(2, N , 10 ** 9 + 7))

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
S = np.array(list(S))
a = np.zeros(N)
a[S == 'I'] = 1
a[S == 'D'] = -1
print(max(0, int(a.cumsum().max())))


Measured memory_bytes: 13608
#include <iostream>
#include <map>
#include <tuple>
#include <vector>
using namespace std;

int root(int x, vector<int> &v){
        return v[x]==x ? x : v[x]=root(v[x], v);
}

void unit(int x, int y, vector<int> &v, vector<int> &r){
        x = root(x, v);
        y = root(y, v);
        if(x==y) return;
        if(r[x]<r[y]) v[x] = y;
        else{
                v[y] = x;
                if(r[x]==r[y]) ++r[x];
        }
        return;
}

int main(){
        int N,K,L,i,t1,t2;
        cin >> N >> K >> L;
        vector<int> p1(N);
        vector<int> p2(N);
        vector<int> r1(N, 1);
        vector<int> r2(N, 1);
        map<tuple<int, int>, int> mp;
        for(i=0;i<N;++i){
                p1[i] = i;
                p2[i] = i;
        }
        for(i=0;i<K;++i){
                cin >> t1 >> t2;
                --t1; --t2;
                unit(t1, t2, p1, r1);
        }
        for(i=0;i<L;++i){
                cin >> t1 >> t2;
                --t1; --t2;
                unit(t1, t2, p2, r2);
        }
        for(i=0;i<N;++i){
                tuple<int, int> t = make_tuple(root(i, p1), root(i, p2));
                ++mp[t];
        }
        for(i=0;i<N;++i){
                tuple<int, int> t = make_tuple(root(i, p1), root(i, p2));
                cout << mp[t] << " ";
                if(i==N-1) cout << endl;
        }

        return 0;
}

Measured memory_bytes: 15104
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <cctype>
#include <queue>
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define REP1(j,n) for(int j=0;j<(int)n;++j)
#define REPD(i,n) for(int i=n;i>=0;--i)
#define REPD1(j,n) for(int j=n;j=>0;--j)
#define REPS(i,n) for(int i=1;i<=(int)n;++i)
#define REPS1(j,n) for(int j=1;j<=(int)n;++j)
#define rep(i,a,n) for(int i=a;i<=(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;
const ll INF=1e9+7;

int main(void) {
	int n;
	cin >> n;
	int x = n * 800;
	int y = n / 15 * 200;
	cout << x - y << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int a,b;
    cin >> a >> b;
    if(a > b){
        for(int i=0;i<a;i++) cout << b;
        cout << endl;
    } else {
        for(int i=0;i<b;i++) cout << a;
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (ll)((v).size())
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define tihs if(fopen("inp.txt","r"))freopen("inp.txt", "r", stdin),freopen("out.txt", "w", stdout);
using namespace std;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 


#define M 100010




int main(){
    IOS;
    tihs;
    
   	ll n,k;cin>>n>>k;
   	ll cnt[n+1]={0};
   	rep(i,0,k){
   		ll d;cin>>d;
   		rep(j,0,d){
   			ll x;cin>>x;
   			cnt[x]++;
   		}
   	}
   	ll c=0;
   	rep(i,1,n+1)if(!cnt[i])c++;
   	cout<<c;


    return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using ll = long long;
using namespace std;
int main(){
ll n,m,x;
cin>>n>>m>>x;
ll a, left=0,right=0;
rep(i,m){
    cin>>a;
    if(a>x) right++;
    else left++;
}
cout<<min(left,right)<<endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/*Atcoder用
 * 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = br.readLine().split(" ");
		int a = Integer.parseInt(tmp[0]);
		int b = Integer.parseInt(tmp[1]);
		int c = Integer.parseInt(tmp[2]);


		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String get = br.readLine();
		char[] s = get.toCharArray();
		for(char c:s)System.out.println(c);

		List<Integer> ls = new ArrayList<Integer>();
		String[] tmp = br.readLine().split(" ");
		for (int n = 0; n < N; n++) {
			ls.add(Integer.parseInt(tmp[n]));
		}
 */

public class Main {
	static List<Integer> money6 = new ArrayList<Integer>();
	static List<Integer> money9 = new ArrayList<Integer>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = br.readLine().split(" ");
		int N = Integer.parseInt(tmp[0]);



		for (int i = 6;i>=1;i--){
			money6.add((int)Math.pow(6, i));
		}
		for(int j = 5; j>=1;j--){
			money9.add((int)Math.pow(9, j));
		}
		Main m = new Main();

		int i = m.hukasa(0,N);
		System.out.println(i);

	}

	int hukasa(int c,int now){	//c...count,now...nowMoney
		if(now<9 && now >=6){
			return c + (now-6) + 1;	//countを返す
		}else if(now < 6 && now >= 0){
			return c+now;
		}else if(now<0){
			return 10000;
		}else{
			int ret6 = 0;
			int ret9 = 0;

			for(int i = 0;i<money6.size();i++){
				if(now>=money6.get(i)){
					ret6 = money6.get(i);
					break;
				}
			}
			for(int j = 0;j<money9.size();j++){
				if(now>=money9.get(j)){
					ret9 = money9.get(j);
					break;
				}
			}

			//TODO:count+1,深さ探索
			int i = hukasa(c+1,now-ret6);
			int j = hukasa(c+1,now-ret9);

			return (Math.min(i, j));



		}
	}
}


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

void qsort(int* data, int first, int last){
	if (first == last) return;
	int k = data[first];
	int tmp = first;
	int left = first, right = last-1;
	while (left < right){
		while (left < right && data[right] >= k) right--;
		data[tmp] = data[right]; 
		tmp = right;
		while (left < right && data[left] <= k) left++; 
		data[tmp] = data[left];
		tmp = left;
	}
	data[tmp] = k;
	qsort(data, first, tmp);
	qsort(data, tmp+1, last);
}

int min_mul(int m, int n){
	if (n == 0) return m;
	else
		min_mul(n, m % n);
}

int max_mul(int m, int n){
	return m*n/min_mul(m,n);
}




int main(){
	int n;
	cin>>n;
	int* data = new int(n);
	for(int i=0;i<n;i++)
		cin>>data[i];
	qsort(data,0,n);
	int ans = data[0];
	for(int j=1;j<n;j++){
		ans = max_mul(ans,data[j]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3096
import numpy as np
H, W = [int(i) for i in input().split()]
ai = [list(input()) for i in range(H)]
arr = np.asarray(ai)
for x in range(H):
  if '#' not in arr[x,:]:
    arr[x,:] = 'a'
for y in range(W):
  if '#' not in arr[:,y]:
    arr[:,y] = 'a'
for x in range(H):
  str = ''
  for y in range(W):
    if arr[x,y] != 'a':
      str += arr[x,y]
    else:
      pass
  if str != '':
    print(str)
  else:
    pass

Measured memory_bytes: 12532
#include <string>
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int main(){
	string s; cin>>s;
	map<char,int> mp;
	for(int i = 0; i < s.size(); i++){
		mp[s[i]]++;
	}

	cout << min(min(mp['K'],mp['U']),min(mp['P'],mp['C'])) << endl;
}

Measured memory_bytes: 1192
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
typedef long long ll;

bool sec_dp[1005][1005];
bool det_false[1005][1005];
ll dp[1005]={0};
ll rsum[1005]={0};
ll c[1005]={0},w[1005]={0};
bool get_sec_dp(ll i,ll j){
  if(i==j) return sec_dp[i][j]=true;
  if(sec_dp[i][j]) return true;
  if(det_false[i][j]) return false;
  bool f1=get_sec_dp(i+1,j);
  if(f1&&rsum[j]-rsum[i]<=c[i]) return sec_dp[i][j]=true;
  bool f2=f2=get_sec_dp(i,j-1);
  if(rsum[j-1]-rsum[i-1]<=c[j]&&f2) return sec_dp[i][j]=true;
  det_false[i][j]=true;
  return false;
}

int main(){
  ll n;
  scanf("%lld",&n);
  for(int i=1;i<=n;i++) scanf("%lld%lld",&c[i],&w[i]);
  //for(int i=1;i<=n;i++) cout<<c[i]<<" "<<w[i]<<endl;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++) {
      sec_dp[i][j]=false;
      det_false[i][j]=false;
    }
    dp[i]=174417441744;
    rsum[i]=rsum[i-1]+w[i];
  }
  dp[0]=0;
//  get_sec_dp(1,n);
  /*for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++) cout<<(sec_dp[i][j]?"O":"X");
    cout<<endl;
  }*/
  for(int i=0;i<n;i++){
    for(int j=i+1;j<=n;j++){
      if(get_sec_dp(i+1,j)){
        dp[j]=min(dp[i]+1,dp[j]);
      }
    }
  }
  printf("%lld\n",dp[n]);
}



Measured memory_bytes: 5240
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

a = k()
b=k()
c = k()
d = k()
print(min(a,b)+min(c,d))


Measured memory_bytes: 10336
#include <bits/stdc++.h>
//#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int LL;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
#define SORT(v) sort(v.begin(),v.end())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
//template<class T>void max(T a,T b){if(a<b)return b;else return a;}
//template<class T>void min(T a,T b){if(a>b)return b;else return a;}
//template<class T>bool Max(T&a, T b){if(a < b){a = b;return 1;}return 0;}
//template<class T>bool Min(T&a, T b){if(a > b){a = b;return 1;}return 0;}

//////////////////////////


int main(){fastio
    string s;cin>>s;
    ll d;cin>>d;
    ll n=s.size();
    ll dp[n][2][d];memset(dp,0,sizeof(dp));
    rep(i,0,s[0]-'0'){
        if(i==s[0]-'0')dp[0][1][i%d]=1;
        else Add(dp[0][0][i%d],1);
    }
    rep(i,0,n-2){
        rep(j,0,d-1){
            rep(k,0,9){
                Add(dp[i+1][0][(j+k)%d],dp[i][0][j]);
            }
            rep(k,0,s[i+1]-'0'){
                if(k==s[i+1]-'0')Add(dp[i+1][1][(j+k)%d],dp[i][1][j]);
                else Add(dp[i+1][0][(j+k)%d],dp[i][1][j]);
            }
        }
    }
    ll ans=0;
    rep(j,0,1)Add(ans,dp[n-1][j][0]);
    cout<<mod(ans-1)<<endl;
    
    return 0;
}



Measured memory_bytes: 15872
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
int K;
int N;
int A[200000+1];
int d[200000];
int main(){
  int i;
  rd(K);
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  A[N] = A[0] + K;
  for(i=(0);i<(N);i++){
    d[i] = A[i+1] - A[i];
  }
  {
    int RZTsC2BF;
    int FmcKpFmN;
    if(N==0){
      FmcKpFmN = 0;
    }
    else{
      FmcKpFmN = d[0];
      for(RZTsC2BF=(1);RZTsC2BF<(N);RZTsC2BF++){
        FmcKpFmN = max_L(FmcKpFmN, d[RZTsC2BF]);
      }
    }
    wt_L(K -FmcKpFmN);
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20200322-1 [beta]

// --- original code ---
// int K, N, A[2d5+1];
// int d[2d5];
// {
//   rd(K,N,A(N));
//   A[N] = A[0] + K;
//   rep(i,N) d[i] = A[i+1] - A[i];
//   wt(K - max(d(N)));
// }


Measured memory_bytes: 2816
import sys
input = sys.stdin.readline

edges = {}
node_count = 0
node_seen = set()
edge_list = []

def dfs(t_node, t_edge):
    global node_count, node_seen
    node_count += 1
    node_seen.add(t_node)
    next_nodes = set(edges[t_node]) - node_seen
    if len(next_nodes) == 0:
        return
    else:
        for nextn in next_nodes:
            if t_node in t_edge and nextn in t_edge:
                pass
            else:
                dfs(nextn, t_edge)

def main():
    global edges, node_count, node_seen, edge_list
    n, m = map(int, input().split())
    all_nodes = set([i for i in range(1, n + 1)])
    edges = {e: [] for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].append(g)
        edges[g].append(s)
        edge_list.append((s, g))
    # 処理
    r = 0
    for itry in range(m):
        node_seen = set()
        node_count = 0
        dfs(edge_list[itry][0], edge_list[itry])
        r += all_nodes != node_seen

    print(r)

if __name__ == '__main__':
    main()


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

int main(){
    int A[5];
    for(int i=0;i<5;i++){
        cin >> A[i];
    }
    int k;
    cin >> k;
    for(int i=0;i<5;i++){
        for(int j=i;j<5;j++){
            int res = A[j]-A[i];
            if(res>k){
                cout << ":(" << endl;
                return 0;
            }
        }
    }
    cout << "Yay!" << endl;
}

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

const int mxN=3e3+1;
int n, m, dp[mxN][mxN];
string s, t, ans;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> s >> t;
    n=s.size(), m=t.size();
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j) {
            if (s[i-1]==t[j-1])
                dp[i][j]=max(dp[i][j], 1+dp[i-1][j-1]);
            else
                dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
        }
    int i=n, j=m, cur=dp[n][m];
    while (i && j) {
        if (s[i-1]==t[j-1])
            ans.push_back(s[i-1]), --i, --j;
        else if (dp[i-1][j]>dp[i][j-1])
            --i;
        else
            --j;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
}


Measured memory_bytes: 38820
def solve():
    N = int(input())
    S = input()

    AW = [0]*(N+1)
    AE = [0]*(N)

    wcount = 0
    ecount = 0
    for i in range(N):
        if S[i] == "W":
            wcount += 1
        else:
            ecount += 1
        AW[i] = wcount
        AE[i] = ecount

    MIN = 1000000

    for i in range(N):
        tmp = 0
        tmp += AW[i-1]
        tmp += AE[-1] - AE[i]
        MIN = min(MIN, tmp)
    print(MIN)

if __name__ == "__main__":
    solve()

Measured memory_bytes: 17568
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define PDD pair<double, double>
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define ctoi(x) (x - 'a') 
#define CTOI(x) (x - 'A')
#define BIT(x) (1 << (x))
using namespace std;

LL modinv(LL a){
    LL b = MOD, u = 1, v = 0;
    while(b){
        LL t = a / b;
        a -= t * b;swap(a, b);
        u -= t * v;swap(u, v);
    }
    u%=MOD;
    if(u < 0) u += MOD;
    return u;

}

LL exp(LL a, LL b){
    LL res = 1;
    LL sum = a;
    while(b){
        if(b&1)res = (res * sum);
        sum = (sum * sum);
        b>>=1;
    }
    return res;
}

double exp(double a, LL b){
    double res = 1;
    double sum = a;
    while(b){
        if(b&1)res = (res * sum);
        sum = (sum * sum);
        b>>=1;
    }
    return res;
}

signed  main(){
    int N;
    cin >> N;
    vector<int> line(N);
    int mincost=INF;
    REP(i, N){
        cin >> line[i];
        mincost = min(mincost, line[i]);
    }
    vector<PII> sorted(N);
    REP(i, N){
        sorted[i].first = line[i];
        sorted[i].second = i;
    }
    sort(ALL(sorted));
    vector<int> place(N);
    REP(i, N){
        place[sorted[i].second] = i;
    }
    int ans = 0;
    vector<char> used(N, false);
    REP(i, N){
        if(used[i])continue;
        if(i == place[i])continue;
        int nmin = line[i];
        int sum = 0;
        int count = 0;
        int p = i;
        while(!used[p]){
            nmin = min(nmin, line[p]);
            sum += line[p];
            used[p] = true;
            p = place[p];
            ++count;
        }
        int dans = sum + (count - 2) * nmin;
        dans = min(dans, mincost * (1 + count) + nmin + sum);
        ans += dans;
    }
    cout << ans << endl;
    return 0;
}




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

const int MOD = 1e9 + 7;

int main() {
    int N, K;  cin >> N >> K;
    long long ans = 0;
    for (long long k = K; k <= N + 1; ++k) {
        ans = (ans + k * (2 * N - k + 1) / 2 - (k - 1) * k / 2 + 1) % MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3604
#include <iostream>
#include <string>
#include <map>

using namespace std;

const int MOD = 2019;

int main(){
	string S;
	cin >> S;

	const int N = S.size();
	map<int, int> m;
	int sum[N + 1] = {0};
	m[0]++;
	{
		int tenpow = 1;
		for (int i = N - 1; i >= 0; i--){
			sum[i] = (sum[i + 1] + (S[i] - '0') * tenpow) % MOD;
			m[sum[i]]++;
			tenpow = (tenpow * 10) % MOD;
		}
	}

	int count = 0;
	for(auto t : m){
		if(t.second > 1){
			count += t.second * (t.second - 1) / 2;
		}
	}

	cout << count << endl;
	return 0;
}


Measured memory_bytes: 4456
a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

n=int(input())
print(a[n-1])


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;

vector<bool> prime(int n){
  vector<bool> is_prime(n, true);
  is_prime[0] = is_prime[1] = false;
  REP(i, n){
    if(!is_prime[i]) continue;
    for(int j = 2; i*j < n; j++){
      is_prime[i*j] = false;
    }
  }
  return is_prime;
}

signed main() {
  int N; 
  cin >> N;

  auto is_prime = prime(60000);

  vector<int> ans;
  REP(i, 55555+1){
    if(is_prime[i] && i%5 == 1) ans.emplace_back(i);
  }

  REP(i, N){
    cout << ans[i]; SPBR(i, N);
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

// #define int ll

#define _GLIBCXX_DEBUG

#define REP(i,n) for (int i = 0; i < (n); ++i)
#define REPD(i,n) for (int i = (n-1); i >= 0; --i)
#define FORE(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define debug(x) cerr << #x << ": " << x << '\n'
#define hyphen() cerr << "--\n"

#define ALL(vec) (vec).begin(), (vec).end()
#define REVALL(vec) (vec).rbegin(), (vec).rend()

#define fst first
#define snd second
#define pb push_back

const int MOD = (int)1e9 + 7;
const int INF = numeric_limits<int>::max();
const int BIT = 10;

signed main() {
    int N, M;

    cin >> N >> M;

    vector<int> Ks(M);
    vector<vector<int>> Ss(M, vector<int>(N));
    REP(i, M) {
        int K;
        cin >> K;
        Ks.at(i) = K;

        REP(j, K) {
            int s;
            cin >> s;
            Ss.at(i).at(j) = s - 1;
        }
    }

    vector<int> Ps(M);
    REP(i, M) {
        cin >> Ps.at(i);
    }

    int ans = 0;
    // 全探索
    REP(tmp, (1 << N)) {
        bitset<BIT> bs(tmp);

        bool ok = true;
        REP(m, M) {
            int on = 0;
            REP(k, Ks.at(m)) {
                if (bs.test(Ss.at(m).at(k))) {
                    on += 1;
                }
            }

            if (on % 2 != Ps.at(m)) {
                ok = false;
                break;
            }
        }

        if (ok) {
            ans += 1;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=998244353;
signed main(){
    ll n;cin>>n;
    vector<ll>a(n);
    rep(i,n)cin>>a[i];
    sort(all(a));
    vector<ll>b(1000010);
    ll cnt=0;
    rep(i,n){
        ll k=1;
        if(i){
            if(a[i]==a[i-1])continue;
        }
        if(b[a[i]]==0){
            if(i<n-1&&a[i]==a[i+1])cnt--;
            cnt++;
        }
        while(k*a[i]<=1000010){
            b[k*a[i]]=1;
            k++;
        }
    }
    cout<<cnt<<endl;
}

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

int N,M; //頂点と辺の数
vector<vector<int>> G; //グラフ
vector<int> h; //入次数
vector<int> l_depth; //最大経路長
vector<int> ans; //答えを格納

void input(){
  cin>>N>>M;
  G.resize(N);
  h.resize(N, 0);
  int f,t;
  for(int i=0; i<M; i++){
    cin>>f>>t;
    //f--; t--;
    G[f].push_back(t);
    h[t]++;
  }
}

void topoBFS(){   
  queue<int> unchecked;
  for(int i=0; i<N; i++){
    if(h[i]==0){
      unchecked.push(i);
      l_depth[i] = 0;
    }
  }
  while(!unchecked.empty()){
    int current = unchecked.front();
    unchecked.pop();
    ans.push_back(current);

    for(int next: G[current]){
      h[next]--;
      l_depth[next] = max(l_depth[next], l_depth[current]+1); //最長経路長
      if(h[next]==0){
        unchecked.push(next);
      }
    }
  }
}

int main(){
  input();

  l_depth.resize(N, -1);
  topoBFS();

  bool isDAG = ans.size()==N; //DAGであるかどうか
  if(isDAG){
    for(int x: ans){
      cout<<x<<endl;
    }
  }else{
    cout<<"DAGではない"<<endl;
  }
}


Measured memory_bytes: 3804
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

//定数
//円周率
const double pi = 3.141592653589793238462643383279;
//天井
const int INF = 1000000000; // = 10^9
const ll LINF = 100000000000000000; // = 10^17
//ABC文字列
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZABC";
const string abc = "abcdefghijklmnopqrstuvwxyzabc";
//よくあるmodくん
const ll MOD = 1000000007; // = 10^9 + 7
//前処理テーブルの大きさ指定
const int MAX = 1200000; // = 10^6 + 2*(10^5)
//ちなみに、1024MBで持てる最大長の配列は10^8程度

//データ構造
//隣接リスト用構造体（有向グラフ向け）
struct edge {
  ll to; // E.toでその辺の終点へアクセスできる。
  ll cost; // e.costでその辺の重みにアクセスできる。
};
//Union_Find木
struct UnionFind {
  vector<int> UF; // UF.at(i) : iの親の番号
  vector<int> SIZE; // SIZE.at(root(i)) : iと連結されてる要素の数
  UnionFind(int N) : UF(N), SIZE(N, 1) { // 最初は全てが根であるとして初期化
    for(int i = 0; i < N; i++) {
      UF.at(i) = i;
    }
  }
  int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (UF.at(x) == x) {
      return x;
    }
    return UF.at(x) = root(UF.at(x));
  }
  void unite(int x, int y) { // xとyの木を併合
    int rx = root(x); // xの根をrx
    int ry = root(y); // yの根をry
    if (rx == ry) {
      return; // xとyの根が同じ(=同じ木にある)時はそのまま
    }
    // xとyの根が同じでない(=同じ木にない)時：小さい方の根を大きい方の根につける。
    if (SIZE.at(rx) < SIZE.at(ry)) {
      UF.at(rx) = ry;
      SIZE.at(ry) += SIZE.at(rx);
      SIZE.at(rx) = 0;
    }
    else {
      UF.at(ry) = rx;
      SIZE.at(rx) += SIZE.at(ry);
      SIZE.at(ry) = 0;
    }
  }
  bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す。
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
  int size(int x) { // xと連結されてる要素の数を返す。
    return SIZE.at(root(x));
  }
};

//関数 (計算量)
//ctoi (O(1))
int ctoi(char c){
  if (c == '0') return 0;
  if (c == '1') return 1;
  if (c == '2') return 2;
  if (c == '3') return 3;
  if (c == '4') return 4;
  if (c == '5') return 5; 
  if (c == '6') return 6;
  if (c == '7') return 7;
  if (c == '8') return 8;
  if (c == '9') return 9;
  return -1;  
}
//to_char (O(1))
char to_char(int i){
  if (i == 0) return '0';
  if (i == 1) return '1';
  if (i == 2) return '2';
  if (i == 3) return '3';
  if (i == 4) return '4';
  if (i == 5) return '5';
  if (i == 6) return '6';
  if (i == 7) return '7';
  if (i == 8) return '8'; 
  if (i == 9) return '9';
  return ' ';  
}

// A^N mod M を計算する。modしたくなかったらM = LINFとかにすればよい。(O(√N))
ll modpow(ll A, ll N, ll M) {
  ll ans = 1;
  while (N > 0) {
    if (N & 1) ans = ans * A % M;
      A = A * A % M;
      N >>= 1;
   }
  return ans;
}

//メイン処理
int main() {
  cout << fixed << setprecision(16); //精度向上
  //ここまでテンプレ
  int N;
  cin >> N;
  vector<ll> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  vector<vector<ll>> DP(N, vector<ll>(2, -LINF));
  DP.at(0).at(0) = A.at(0);
  for (int i = 1; i < N; i++) {
    DP.at(i).at(0) = max(DP.at(i - 1).at(0), DP.at(i - 1).at(1)) + A.at(i);
    DP.at(i).at(1) = max(DP.at(i - 1).at(0) - 2 * A.at(i - 1) - A.at(i), 
                         DP.at(i - 1).at(1) + 2 * A.at(i - 1) - A.at(i));
  }
  cout << max(DP.at(N - 1).at(0), DP.at(N - 1).at(1)) << endl;
}

Measured memory_bytes: 9568
import java.util.*;
class Main {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    String s=sc.next();
    String t=sc.next();
    int n=s.length();
    int count=0;
    for(int i=0;i<n;i++){
      if(s.charAt(i)!=t.charAt(i)){
        count=count+1;
      }
    }
    System.out.print(count);
  }
}

Measured memory_bytes: 41464
import math


def read():
    N = int(input())
    A = list(map(int, input().split()))
    return N, A

def solve(N, A):
    C = [0 for i in range(N)]
    for a in reversed(A):
        C[a-1] += 1
    for c in C:
        print(c)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))


Measured memory_bytes: 33616
#include <iostream>

using std::cin;
using std::cout;
using std::endl;
using std::max;
using std::min;

static int
ggd(int a, int b)
{
  int m = max(a, b);
  int n = min(a, b);
  for (;;)
  {
    int r = m % n;
    if (r == 0)
    {
      break;
    }
    m = n;
    n = r;
  }
  return n;
}

static long
lcm(int a, int b)
{
  return (long)a * b / ggd(a, b);
}

static long
count(long A, long B, long div)
{
  long top = (A + div - 1) / div;
  long bot = B / div;
  return bot - top + 1;
}

int
main()
{
  long A, B;
  int C, D;
  cin >> A >> B >> C >> D;
  cout << (B - A + 1) - count(A, B, C) - count(A, B, D) + count(A, B, lcm(C, D)) << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
from bisect import bisect_left

def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

input = sys.stdin.readline
N = int(input())
A = []
for _ in range(N):
	A.append(int(input()))

multi_lis = []
for a_i in A:
    if not multi_lis:
        multi_lis.append(a_i)
        continue

    if a_i <= multi_lis[-1]:
        multi_lis.append(a_i)
    else:
        p = bisect_right_reverse(multi_lis, a_i)
        multi_lis[p] = a_i 

print(len(multi_lis))

Measured memory_bytes: 82736
class Tree:
    def __init__(self):
        self.parent = None
        self.left = None
        self.right = None
        self.key = -1


def preparse(u):
    if u is None: return
    print(" ", end="")
    print(u.key, end="")
    preparse(u.left)
    preparse(u.right)


def inparse(u):
    if u is None: return
    #???????????????????§????
    inparse(u.left)
    #??¨???
    print(" ", end="")
    print(u.key, end="")
    #??????????§????
    inparse(u.right)


def insert(key):
    global root
    y = None
    sch = root
    # ?????\????±?Node?????????
    z = Tree()
    z.key = key

    while sch is not None:
        # ???????????????tree????????????????????§?????°??????Key??????????´?(y)?????¢??????
        y = sch
        # key?????¢??????tree????´????key??????????°????????????°??????????´¢?????§???????????°??????????´¢
        sch = sch.left if key < sch.key else sch.right

    # ???????´??±????
    z.parent = y

    if y is None:
        root = z
    else:
        if key < y.key:
            # ???????´??????????????°????????????°????????´???????´??????????
            y.left = z
        else:
            # ???????´???????????????§???????????°????????´???????´??????????
            y.right = z

    # ???????????????
    trees.append(z)


def find(key):
    sch = root
    while sch is not None and sch.key != key:
        if key < sch.key: sch = sch.left
        else: sch = sch.right

    if sch is not None and sch.key == key: return True
    else: return False


def showresult():
    inparse(root)
    print("")
    preparse(root)
    print("")


N = int(input())
# ?????????
trees = []
root = None

for i in range(N):
    l = list(input().split())
    com = l[0]
    if com == "insert":
        key = int(l[1])
        # ????´???????????¨????
        insert(key)
    elif com == "print":
        showresult()
    elif com == "find":
        key = int(l[1])
        if find(key):
            print("yes")
        else:
            print("no")

Measured memory_bytes: 127904
#include<stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
 
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(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())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 
int main(void){
    int n, m;
    cin >> n >> m;
    double res = 0;
    int x = 1900 * m + 100 * (n - m);
    double p = pow(2, m);
    cout << (int)(x * p) << endl;
    return 0;
}



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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 1000000007
using ll = long long;

int main(){
    string K; int D;
    cin>>K>>D;
    // ll dp[100010][100][2];//dp[keta][%D][smaller]
    vector<vector<vector<ll>>> dp(100010,vector<vector<ll>>(100,vector<ll>(2,0)));
    int L = K.size();
    //DP初期化
    dp[0][0][1] = 0;
    dp[0][0][0] = 1;
    vector<int> k;
    rep(i,L)k.push_back((int)(K[i]-'0'));
    //桁DPは配るDPで書いた方がわかりやすい。
    rep(keta,L){
        rep(mod,D){
            rep(digit,10){
                dp[keta+1][(mod+digit)%D][1] = (dp[keta+1][(mod+digit)%D][1] + dp[keta][mod][1]%MOD)%MOD;
            }
            rep(digit,k[keta]){
                dp[keta+1][(mod+digit)%D][1] = (dp[keta+1][(mod+digit)%D][1] + dp[keta][mod][0]%MOD)%MOD;
            }
            dp[keta+1][(mod+k[keta])%D][0] = (dp[keta+1][(mod+k[keta])%D][0] + dp[keta][mod][0]%MOD)%MOD;                
        }
    }
    cout<<(dp[L][0][1]+dp[L][0][0]-1+MOD)%MOD<<endl;
}


Measured memory_bytes: 554216
using System;

namespace abc107_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] array = Console.ReadLine().Split(' ');
            int NumberOfTrain = int.Parse(array[0]);
            int IndexTrain = int.Parse(array[1]);
            int answer = 0;
            answer = NumberOfTrain - IndexTrain + 1;
            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 13140