akhauriyash/Code-Regression huggingface dataset:
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////        ////////////        ////////////        ////////////        ////////////        ////////////        ///
////////  /////  ///////////  /////  ///////////  /////  ///////////  /////  ///////////  /////  ///////////  /////  ///
///////  /////  ///////////  /////  ///////////  /////  ///////////  /////  ///////////  /////  ///////////  /////  ////
//////        ////////////        ////////////        ////////////        ////////////        ////////////        //////
/////  //////////////////  //////////////////  //////////////////  //////////////////  //////////////////  /////////////
////  //////////////////  //////////////////  //////////////////  //////////////////  //////////////////  //////////////
///  //////////////////  //////////////////  //////////////////  //////////////////  //////////////////  ///////////////
//  //////////////////  //////////////////  //////////////////  //////////////////  //////////////////  ////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

a;f;n;s;u;v;w;C[37000];D[3001][3001];M[3001];*c=C;
main(m){
  for(;++n%3+scanf("%d",&w);u=v,w-=v=w)
    for(
      s=2;
      n%3<1&&(
        s<6e3+2?
          n*s++<7?
            *++c=v,*++c=w,*++c=1e7
          :u-v|v-w?
            *++c=u,*++c=s/3,*++c=fmax(v-w?:D[s/3][v]+1,M[s/3]),
            *++c=u,*++c=v,*++c=fmax(D[w][w]+1,m)
          :++f
        :c>C&&(
          w=*c--,v=*c--,u=*c--,
          D[u][v]>w||(D[u][v]=D[v][u]=w),M[u]>w||(M[u]=w),M[v]>w||(M[v]=w),m=m>w?m:w
        )
      );
      u=v,v=w,w=a
    )a=u;
  printf("%d",m+=f/6e3-1e7);
}


Measured memory_bytes: 25716
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;


int main(){
  int n, m;
  cin >> n >> m;
  vector<pii> ab(n);
  ll value=0;
  
  for(int i=0; i<n; i++){
  	cin >> ab[i].first >> ab[i].second;
  }
  
  sort(ab.begin(), ab.end());
  
  for(int i=0; i<n; i++){
    if(ab[i].second < m){
      value += ab[i].first*ab[i].second;
      m -= ab[i].second;
    }
    else{
      value += ab[i].first*m;
      goto loopend;
    }
  }
  
loopend:  
  cout << value << endl;
  return 0;
}

Measured memory_bytes: 1792
/*
          Life before Death
          Strength before Weakness
          Journey before Destination
    */
    
    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    #define rep(i,a,n) for(ll i=a;i<n;i++)
    #define per(i,n,a) for (ll i=n;i>a;i--)
    #define te ll t; std::cin >> t; while(t--)
    #define SZ 100011
    //#define M_PI  3.141592653589793238462643383279502884L
    /*------Just DO IT--------------------------------------*/

    ll dp[SZ];

    ll solve(){
      ll n,k;
      cin>>n>>k;
      ll a[n+1];
      rep(i,1,n+1) cin>>a[i], dp[i] = 1e9;
      //rep(i,0,k) dp[2] = abs(a[2] - a[])
      dp[1] = 0;
      dp[2] = abs(a[2]-a[1]);
      rep(i,3,n+1) {
      rep(j,0,min(i,k+1)) dp[i] = min( dp[i], dp[i-j] + abs(a[i-j] - a[i]));
      }cout<<dp[n]<<endl;
    } 
    
   int main() {
       fastio
       solve();
    }

Measured memory_bytes: 1792
#include <stdio.h>
#include <math.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define in_arr(type, a, n) for(int i = 0; i < n; i++) scanf(type, &((a)[i]));

int main(){
    int a, b, c, x, ret = 0;
    scanf("%d%d%d%d", &a, &b, &c, &x);
    for(int i = 0; i <= a; ++i){
        for(int j = 0; j <= b; ++j){
            for(int k = 0; k <= c; ++k){
                if(i * 500 + j * 100 + k * 50 == x){
                    ++ret;
                }
            }
        }
    }
    printf("%d\n", ret);
    return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int a[20], x[20][20], y[20][20];
	int i, j, k;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		for (j = 0; j < a[i]; j++)
		{
			scanf("%d %d", &x[i][j], &y[i][j]);
			x[i][j]--;
		}
	}
	int max = 1;
	for (i = 0; i < n; i++)
		max *= 2;
	int p, q[20];
	int v, ans = 0;
	for (k = 0; k <= max; k++)
	{
		p = k;
		for (j = 0; j < n; j++)
		{
			if (p % 2 > 0)
				q[j] = 1;
			else
				q[j] = 0;
			p /= 2;
		}
		v = 0;
		for (i = 0; i < n; i++)
		{
			if (q[i] > 0)
			{
				for (j = 0; j < a[i]; j++)
				{
					if (q[x[i][j]] > 0 && y[i][j] == 0)
						v++;
					if (q[x[i][j]] == 0 && y[i][j] > 0)
						v++;
				}
			}
		}
		if (v == 0)
		{
			for (i = 0; i < n; i++)
				if (q[i] > 0)
					v++;
			if (ans < v)
				ans = v;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        foreach (var a in A)
        {
            if (a % 2 == 0)
            {
                if (a % 3 != 0 && a % 5 != 0)
                {
                    Console.WriteLine("DENIED");
                    return;
                }
            }
        }

        Console.WriteLine("APPROVED");
    }
}

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

using namespace std;

#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define endl '\n'
#define snd second
#define fst first
#define fastio cin.tie(NULL),cout.sync_with_stdio(true)

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector <int> vi;
typedef pair <ll, int> ii;
typedef pair <ii,int> iii;

const int mod = 1e9 + 7;
const int N = 100005;

void solve(){
	int ans;
	for(int i = 1; i <= 5; i++){
		int x; cin >> x;
		if(x == 0)ans = i;
	}
	cout << ans << endl;
}

int main(){
	fastio;
	int t = 1;
	//cin >> t;
	while(t--)
		solve();
	return 0;
}


Measured memory_bytes: 3620
import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        sc.close();
        if(n<10) System.out.println("ABC00"+n);
        else if(n<100) System.out.println("ABC0"+n);
        else System.out.println("ABC"+n);
    }
    
}


Measured memory_bytes: 23764
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;

vector<int> v, parent, depth;

int find(int a){
  if(parent[a] == a) return a;
  else return parent[a] = find(parent[a]);
}

void merge(int a, int b){
  int pa = find(a), pb = find(b);
  if(pa == pb) return ;

  if(depth[pa] > depth[pb]) swap(pa, pb);
  if(depth[pa] == depth[pb]) ++depth[pa];
  parent[pb] = pa;
}

bool same(int a, int b){
  return find(a) == find(b);
}

void init_union_find(int V){
  v = vector<int>(V);
  parent = vector<int>(V);
  depth = vector<int>(V, 1);
  REP(i, V) parent[i] = i;
}

struct edge {
  int f, t, c;
  bool operator < (const edge &e) const { return c < e.c; };
};

int kruskal(int V, int E, vector<edge> es){
  sort(es.begin(), es.end());
  init_union_find(V);
  int min_cost = 0;
  REP(i, E){
    if(!same(es[i].f, es[i].t)){
      min_cost += es[i].c;
      merge(es[i].f, es[i].t);
    }
  }
  return min_cost;
}

int main() {
  int V, E;
  while(cin >>V >>E && V){
    vector<edge> es(E);
    REP(i, E) cin >>es[i].f >>es[i].t >>es[i].c;
    cout <<kruskal(V, E, es) <<endl;
  }
  return 0;
}

Measured memory_bytes: 1224
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner s = new Scanner(System.in);
    int a = s.nextInt();
    int b = s.nextInt();

    if(a >= 13){
      System.out.println(b);
    }else if(a >= 6 && a <= 12){
      System.out.println(b / 2);
    }else if(a <= 5){
      System.out.println(0);
    }
  }
}


Measured memory_bytes: 21204
from sys import stdin, stdout  
  
# suppose a function called main() and 
# all the operations are performed 
def main(): 
  
    # input via readline method 
    n = stdin.readline() 
  
    # array input similar method 
    arr = [int(x) for x in stdin.readline().split()] 
  
    #initialize variable 
    summation = 1
    for x in arr:
        if x==0:
            summation=0
            break
    # calculate sum 
    for x in arr: 
        summation *= x
        if summation>1e18:
            summation=-1
            break
  
    # could use inbuilt summation = sum(arr) 
    if summation>1e18:
        print("-1");
    else:
        print(summation);


    # print answer via write 
    # write method writes only 
    # string operations 
    # so we need to convert any 
    # data into string for input 
    
  
# call the main method 
if __name__ == "__main__": 
    main()     

Measured memory_bytes: 22768
import java.io.*;
import java.util.*;

public class Main {

	final static long MOD = 1000000007;
	public static void main(String[] args) throws Exception {
		// TODO 自動生成されたメソッド・スタブ

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String W = in.readLine();
		String[] Ws = W.split(" ");
		int N = Integer.parseInt(Ws[0]);
		int K = Integer.parseInt(Ws[1]);

		W = in.readLine();
		Ws = W.split(" ");

		long[] H = new long[Ws.length];
		for (int i = 0; i < Ws.length; i++) {
			H[i] = Long.parseLong(Ws[i]);
		}

		Arrays.sort(H);
		long sum=0;
		for(int i=N-1-K;i>=0;i--){
			sum+=H[i];
		}

		System.out.println(sum);
	}
}


Measured memory_bytes: 68908
#include<iostream>
#include<algorithm>
using namespace std;
char ch[3][106];
int n , res;
int main(){
	//freopen("input","r",stdin);
  	cin >> n;
	cin >> ch[0] >> ch[1] >> ch[2];
	for( int i = 0 ; i < n ; ++ i ) {
		if( ch[0][i] == ch[1][i] && ch[0][i] == ch[2][i] ) continue;
		else if( ch[0][i] == ch[1][i] || ch[0][i] == ch[2][i] || ch[1][i] == ch[2][i] ) ++res;
		else res += 2;
	}
	cout << res;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int prime(int n)
{
    //cout<<"fksalj|"<<endl;
    int cnt=0;
    for(int i=2; i<n; i++)
    {
        if(n%i==0)
        {
            cnt++;
            break;
        }
    }
    //cout<<cnt<<endl;
    if(cnt==0)
    {
        cout<< n<<endl;
    }

    else
    {
        n++;
        prime(n);
    }


}
int main()
{
    int n;
    cin>>n;
    if(n==2)
    {
        cout<<2<<endl;
    }
    else
    {
        //cout<<"asd;jf"<<endl;
        prime(n);
    }

}


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

typedef long long LL;  
using namespace std;

#define fillchar(a, x) memset(a, x, sizeof(a))
#define MP make_pair
#define PB push_back
#define endl '\n'

const LL M = 1e17;

int main()
{
ios_base::sync_with_stdio(0); 
cout.precision(15);
cout.setf(ios::fixed);

LL n,i,j,m;

cin>>n;

vector <LL> v(n);

for(i=0;i<n;i++)
	cin>>v[i];
LL mi = M;
for(i=-100;i<=100;i++)
	{
	LL sum  = 0;
	
	for(j=0;j<n;j++)
		sum += (v[j]-i)*(v[j]-i);
	mi = min(mi,sum);
	}
cout<<mi<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
        int n=0,i;
        char a[4];
        scanf("%s",a);
        for(i=0;i<4;i++){
                if(a[i]=='+') n++;
                else if(a[i]=='-') n--;
        }
        printf("%d",n);
        return 0;
}


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

const int N = 2020202;

inline char get(void) {
	static char buf[100000], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, 100000, stdin);
		if (S == T) return EOF;
	}
	return *S++;
}
template<typename T>
inline void read(T &x) {
	static char c; x = 0; int sgn = 0;
	for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
	for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
	if (sgn) x = -x;
}

int n, k, m, ans, cnt;
int a[N], b[N], c[N];

int main(void) {
	read(n); read(k);
	for (int i = 1; i <= n; i++) {
		read(a[i]); ++b[a[i]];
		if (b[a[i]] == 1) ++m;
	}
	for (int i = 1; i <= n; i++)
		if (b[i] > 0) c[++cnt] = b[i];
	sort(c + 1, c + cnt + 1);
	for (int i = 1; i <= m - k; i++)
		ans += c[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9344
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

S = list(input())
N = len(S)

cnt = 0
for i in range(len(S)-1):
	if S[i]==S[i+1]:
		cnt += 1
		S[min(len(S)-1, i+2)] = "_"

print(N-cnt)


Measured memory_bytes: 11984
#include<stdio.h>
int main(){
  int a[300],b[300],i,k,u,H,W;
  for(i=0;i<300;i++){
    scanf("%d%d",&a[i],&b[i]);
    if(a[i]==0 || b[i]==0)break;
  }
  for(k=0;k<i;k++){
    for(H=1;H<=a[k];H++){
      if(H==1 || H==a[k])for(W=0;W<b[k];W++)printf("#");
      else for(W=1;W<=b[k];W++){
	  if(W==1 || W==b[k])printf("#");
	  else printf(".");
	}
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 572
import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                int w = sc.nextInt();
                int n = sc.nextInt();
                int[] values = new int[w];
                for (int i = 0; i < values.length; i++) {
                        values[i] = i + 1;
                }
                for (int i = 0; i < n; i++) {
                        String str = sc.next();
                        String[] ab = str.split(",");
                        int a = Integer.parseInt(ab[0]) - 1;
                        int b = Integer.parseInt(ab[1]) - 1;
                        int c;
                        c = values[a];
                        values[a] = values[b];
                        values[b] = c;
                }
                for(int i=0;i<values.length;i++){
                        System.out.println(values[i]);
                }
        }
}

Measured memory_bytes: 26212
#include<bits/stdc++.h>
#include<limits>
#define ll long long
#define F first
#define S second
#define pb push_back
#define oo (1LL<<63-1)
#define endl '\n'
#define si size()
#define all(v) v.begin(),v.end()
#define FASTIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define Matrix vector< vector < long long > >

using namespace std;

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

const long double Pi=acos(-1),e=2.718;
const int N=2e3+10, mod=1e9+7;
vector<int> G[N];
ll cnt[N];
bool vis[N];

void BFS(int s){
    memset(vis,0,sizeof vis);
    queue<pair<int,int> > q;
    q.push({s,0});
    vis[s]=1;
    while(!q.empty()){
        auto p=q.front();
        q.pop();
        int u=p.F;
        int l=p.S;
        cnt[l]++;
        for(auto v:G[u]){
            if(!vis[v]){
                q.push({v,l+1});
                vis[v]=1;
            }
        }
    }
}
int main ()
{
    FASTIO
    int n,x,y;
    cin >> n >> x >> y;
    for(int i=1;i<=n-1;i++){
        G[i].pb(i+1);
        G[i+1].pb(i);
    }
    G[x].pb(y);
    G[y].pb(x);
    for(int i=1;i<=n;i++){
        BFS(i);
    }
    for(int i=1;i<=n-1;i++){
        cout << cnt[i]/2 << endl;
    }
    return 0;
}
/**

*/


Measured memory_bytes: 384
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));

function main(){
  var n = next();
  var a = [];
  for(var i = 0; i < n; i++){
    a.push([next(),i&1]);
  }
  a.sort((a,b)=>a[0]-b[0]);
  var ans = 0;
  for(var i = 0; i < n; i+=2)if(a[i][1] === 1)ans++;
  return ans;
}

Measured memory_bytes: 52184
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

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

		int n = scanner.nextInt();
		long k = scanner.nextLong();

		int[] list = new int[n];
		HashMap<Integer, Long> bs = new HashMap<Integer, Long>();

		for (int i = 0; i < n; i++) {
			scanner.nextLine();
			int a = scanner.nextInt();
			long b = scanner.nextLong();
			list[i] = a;
			if (bs.containsKey(a)) {
				bs.put(a, (bs.get(a) + b));
			} else {
				bs.put(a, b);
			}
		}
		Arrays.sort(list);
		int ans = 0;
		long sum = 0;
		for (int i = 0; i < n; i++) {
			if (sum >= k) {
				break;
			}
			if (ans == list[i]) {
				continue;
			} else {
				ans = list[i];
				sum += bs.get(list[i]);
			}
		}
		System.out.println(ans);
		scanner.close();
	}
}


Measured memory_bytes: 157092
N = int(input())
S = []

for i in range(N):
  tmp = input().split()
  S.append([(i + 1), tmp[0], int(tmp[1])])

S.sort(reverse=True, key=lambda x:x[2])
S.sort(key=lambda x:x[1])

for s in S:
  print(s[0])

Measured memory_bytes: 3060
a=int(input())
if a<10**9:
  print("0 0 0 "+str(a)+" 1 0")
else:
  if a%(10**9)!=0:
    b=10**9-a%(10**9)
    print("0 0 "+str((a+b)//(10**9))+" "+str(b)+" 1 "+str(10**9))
  else:
    print("0 0 "+str(a//(10**9))+" 0 0 "+str(10**9))

Measured memory_bytes: 3060
import math
x = int(input())
if x == 2 or x == 3:
    print(x)
else:
    i = x
    flag = False
    while i <= 1000000:
        if i % 2 == 0 or i % 3 == 0:
            i += 1
            continue
        for j in range(5, int(math.sqrt(i))+1):
            if i % j == 0:
                break
        else:
            flag = True
        if flag:
            break
        i += 1
    print(i)

Measured memory_bytes: 3064
n,m=map(int,input().split())
g = [[]for _ in range(n)]
for _ in range(m):
    a,b = map(lambda x: int(x) - 1,input().split())
    g[a].append(b)
    g[b].append(a)

dist = [float('inf')]*n
dist[0] = 0

import queue
q = queue.Queue()
q.put([0,0])

while not q.empty():
    cost, nown = q.get()
    for nextn in g[nown]:
        if dist[nextn] != float('inf'):
            continue
        dist[nextn] = nown+1
        q.put([cost + 1,nextn])

for i in range(n):
    if dist[i] == float('inf'):
        print('No')
        exit()
print('Yes')
for i in range(1,n):
    print(dist[i])

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

string change(string s){
    for(int i = s.size() - 1; i > 0; --i){
        swap(s[i],s[i - 1]);
    }

    return s;
}

int main(){
    int n;
    cin >> n;
    long int ans = 0;
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        ans += a - 1;
    }

    cout << ans << endl;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)
const int N_MAX=101010;
int DP[N_MAX][10];
int A[N_MAX], B[N_MAX];

int main(){
    int N, M;
    cin >> N >> M;
    REP(i, M){
        cin >> A[i] >> B[i];
    }
    int Q;
    cin >> Q;
    int c[Q], d[Q], v[Q];
    REP(i, Q){
        cin >> v[i] >> d[i] >> c[i];
    }
    pii dp[N_MAX][11];
    REP(i, Q) dp[v[i]][d[i]] = {i+1, c[i]};
    for(int d=10;d>=1;d--){
        for(int v=1;v<=N;v++){
            dp[v][d-1] = max(dp[v][d-1], dp[v][d]);
        }
        REP(i, M){
            int a = A[i];
            int b = B[i];
            dp[a][d-1] = max(dp[a][d-1], dp[b][d]);
            dp[b][d-1] = max(dp[b][d-1], dp[a][d]);
        }
    }
    REP(i, N) cout << dp[i+1][0].second << endl;
    return 0;
}

Measured memory_bytes: 11264
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include <cmath>
using namespace std;

#define REP(i,n) for(int i=0;(i)<(n);(i)++)
#define ll long long

string S;
int ans;

signed main() {
	cin >> S;

	if (S[0] != 'A') {
		cout << "WA" << endl;
		return 0;
	}

	string ts = S.substr(2, S.length() - 3);
	if (ts.find('C') != ts.rfind('C') || ts.find('C') == string::npos) {
		cout << "WA" << endl;
		return 0;
	}
	
	auto pos = S.find("C");
	for (int i = 1;i < S.length();i++) {
		if (i == pos) continue;
		if (S[i] >= 'A' && S[i] <= 'Z') {
			cout << "WA" << endl;
			return 0;
		}
	}

	cout << "AC" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    
using namespace std;
typedef long long ll;
    
int main()
{
    int A, B, X;
    cin >> A >> B >> X;

    if (X <= A + B && A <= X) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,p,q;
	cin>>n>>p>>q;
	vl c(n+1,0),v(n+1,0);
	rep(i,n){
		cin>>c[i+1];
		v[i+1]=p*i+c[i+1];
	}
	sort(v.begin()+1,v.end());
	partial_sum(all(v),v.begin());
	ll cval=sum(c);
	ll ans=-LINF;

	//puta(v);
	rep(i,n+1){
		ll val=cval+i*p*(q+i-1)-v[i];
		//puta(i,val);
		chmax(ans,val);
	}
	puta(ans);

	return 0;
}


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

int main(){
  int a,b;
  cin >> a >> b;
  int x = a*b/2;
  if(x*2 == a*b){
    cout << "Even" << endl;
  	}
  else{
  	cout << "Odd" << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n,L;
int x[300010],t[300010];
int l[300010],r[300010];
int id[300010];
int main()
{
	scanf("%d %d",&n,&L);
	L*=2;long long ans=0;
	for(int i=1;i<=n;i++)scanf("%d",&x[i]);
	int N=0,num=0,mx=0;
	bool flag=false;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t[i]);
		ans+=(t[i]-1)/L;
		t[i]=(t[i]-1)%L+1;
		l[i]=(L-2*x[i]>=t[i]);
		r[i]=(2*x[i]>=t[i]);
		if(l[i]||r[i])id[++N]=i;
		if(!l[i]||!r[i])ans++;
		if(l[i]&&r[i])num++;
		if(!l[i]&&!r[i])mx=x[i];
		if(r[i]&&!l[i])flag=true;
	}
	int now=0;
	int add=1;
	for(int i=1;i<=N;i++)
	{
		int pos=id[i];
		if(l[pos]&&r[pos])now++;
		else if(l[pos]){
			if(now)now--,num--,add=1;
			else add=0;
		}
	}
	if(!num&&!flag){
		printf("%lld\n",(ans+add)*L);
		return 0;
	}
	add=-1;now=0;
	if(mx>x[id[N]])add=0;
	for(int i=N;i>=1;i--)
	{
		int pos=id[i];
		if(l[pos]&&r[pos])now++;
		else if(r[pos]){
			if(now)now--,num--;
			if(!now)add=0;
		}
	}
	num+=add;
	printf("%lld\n",(ans+(num+1)/2+1)*L);
	return 0;
}

Measured memory_bytes: 6144
#include<bits/stdc++.h>
using namespace std;
#define nl cout<<'\n';
#define ll long long
int arr[100005];
ll dp[100005];
int main()
{

	int n;
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>arr[i];
	}
	dp[1]=0;
	dp[2]=abs(arr[1]-arr[2]);
	for(int i=3;i<=n; i++)
	{
		dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]), dp[i-2]+abs(arr[i]-arr[i-2]));
	}
	cout<<dp[n];
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int c=0;;
    string s;
    cin >> s;
    for(int i=0; i<3; i++)
    {
        if(s[i]=='a')
        {
            c+=1;
        }
        else if(s[i]=='b')
        {
            c+=2;
        }
        else if(s[i]=='c')
        {
            c+=3;
        }
        else{
            c+=0;
        }
    }
    if(c==6)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 256
n, d = map(int, input().split())
x = []
sum_ = 0
count = 0

for ni in range(n):
    e = list(map(int, input().split()))
    x.append(e)

for i in range(n):
    for j in range(i+1,n):
        for k in range(d):
            sum_ += (x[i][k] - x[j][k])**2
        if sum_**0.5 % 1 == 0:
            count += 1
        sum_ = 0

print(count)

Measured memory_bytes: 9232
#include <stdio.h>
#include <stack>
#include <math.h>

using namespace std;

struct Point{
	double x,y;
};

int main(){

	int n;
	scanf("%d",&n);
	double gaiseki;

	bool FLG = true;

	Point points[n],left,right;

	for(int i=0; i < n; i++){
		scanf("%lf %lf",&points[i].x,&points[i].y);
	}

	for(int i=0; i < n; i++){
		if(i == 0){
			right.x = points[1].x - points[0].x;
			right.y = points[1].y - points[0].y;

			left.x = points[n-1].x - points[0].x;
			left.y = points[n-1].y - points[0].y;

			gaiseki = right.x*left.y - right.y*left.x;
		}else if(i == n-1){
			right.x = points[0].x - points[n-1].x;
			right.y = points[0].y - points[n-1].y;

			left.x = points[n-2].x - points[n-1].x;
			left.y = points[n-2].y - points[n-1].y;

			gaiseki = right.x*left.y - right.y*left.x;
		}else{
			right.x = points[i+1].x - points[i].x;
			right.y = points[i+1].y - points[i].y;

			left.x = points[i-1].x - points[i].x;
			left.y = points[i-1].y - points[i].y;

			gaiseki = right.x*left.y - right.y*left.x;
		}
		if(gaiseki < 0){
			FLG = false;
			break;
		}
	}

	if(FLG)printf("1\n");
	else{
		printf("0\n");
	}

    return 0;
}



Measured memory_bytes: 2752
#include<iostream>
#include<vector>
#include<queue>
#include<climits>
using namespace std;

struct edge{
    int s, t, d;
};

int main(){
    int n, m, s;
    cin >> n >> m >> s;
    vector<edge> v;
    for(int i = 0; i < m; i++){
        int s, t, d;
        cin >> s >> t >> d;
        v.push_back(edge({s,t,d}));
    }
    vector<int> dp(n, INT_MAX);
    dp[s] = 0;
    for(int i = 1; i < n; i++){
        vector<int> next(n, INT_MAX);
        for(int j = 0; j < m; j++){
            edge e = v[j];
            if(dp[e.s] != INT_MAX)  next[e.t] = min(next[e.t], dp[e.s] + e.d);
        }
        for(int j = 0; j < n; j++)  next[j] = min(next[j], dp[j]);
        dp = next;
    }
    for(int j = 0; j < m; j++){
        edge e = v[j];
        if(dp[e.s] != INT_MAX && dp[e.t] > dp[e.s] + e.d){
            cout << "NEGATIVE CYCLE" << endl;
            return 0;
        }
    }
    for(int i = 0; i < n; i++){
        if(dp[i] != INT_MAX)    cout << dp[i] << endl;
        else                    cout << "INF" << endl;
    }
    return 0;
}


Measured memory_bytes: 3196
#include<bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	static const ULL M = 1000000007;

	void Solve() {
		UL N; cin >> N;
		vector<ULL> F(N + 1); F[0] = 1;
		for (UL i = 1; i <= N; i++) F[i] = F[i - 1] * i % M;
		ULL X; cin >> X;
		vector<ULL> S(N); rep(i, N) cin >> S[i];
		sort(S.rbegin(), S.rend());
		vector<ULL> dp(X + 1);
		dp[X] = 1;
		rep(i, N) {
			UL t = N - i;
			vector<ULL> buf(X + 1);
			rep(j, X + 1) {
				if (j < S[i]) buf[j] += dp[j] * t;
				else {
					buf[j % S[i]] += dp[j];
					buf[j] += dp[j] * (t - 1);
				}
			}
			rep(j, X + 1) dp[j] = buf[j] % M;
		}
		ULL ans = 0;
		rep(i, X + 1) ans += dp[i] * i % M;
		ans %= M;
		cout << ans << endl;
	}

	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}

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

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

    int C = 6-A-B;
    cout << C;
   
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

//#define DEBUG_ //!!$BDs=P;~$K%3%a%s%H%"%&%H(B!!
#ifdef DEBUG_
#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

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

    template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int mod = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);
const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899;


signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);
    int N; cin >> N;
    VL A(N),B(N),D(N);
    LL acc = 0;
    LL gain = 0, ans = 0;

    REP(i,N) {
        cin >> A[i] >> B[i];

        acc += A[i];
        D[i] = A[i] - B[i];
        if(A[i] < B[i]) {
            gain += B[i] - A[i];
        }
    }
    if(gain == 0) {
        cout << 0 << endl;
        return 0;
    }
    REP(i,N){
        if(D[i] <= 0) continue;

        chmax(ans, acc-A[i] + D[i]);
        
    }
    cout << ans << endl;

}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
#define ld long double
int main(){
    int x;
    cin>>x;
    YN(x>=30);
}

Measured memory_bytes: 3612
package main

import (
	"fmt"
	"math"
)

func sumPlaces(a int) int {
	var sum int
	if a < 10 {
		sum = a
	} else {
		tmp := a
		for tmp != 0 {
			sum += tmp % 10
			tmp /= 10
		}
	}
	return sum
}
func main() {
	var N int
	fmt.Scan(&N)
	var A, B, min int
	min = math.MaxInt32
	for A = 1; A < N; A++ {
		B = N - A
		sumA := sumPlaces(A)
		sumB := sumPlaces(B)
		if min > (sumA + sumB) {
			min = sumA + sumB
		}
	}
	fmt.Println(min)
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

    string ans = "No";
    for(int i=0; i< (int)st.size(); ++i){
        if(st[i] == '7') ans = "Yes";
    }

    cout << ans << endl;
}

Measured memory_bytes: 3616
/*hello! guys~*/
#include<bits/stdc++.h>
using namespace std;
string str; 
string intToA(int n,int radix)    //n是待转数字，radix是指定的进制
{
    string ans="";
    do{
        int t=n%radix;
        if(t>=0&&t<=9)    ans+=t+'0';
        else ans+=t-10+'a';
        n/=radix;
    }while(n!=0);    //使用do{}while（）以防止输入为0的情况
    reverse(ans.begin(),ans.end());
    return ans;    
}
int main()
{
long long n,k,o;
int i;
cin>>n>>k;
str=intToA(n,k);
    printf("%d",str.size());
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define srep(i, l, r) for (register int i = l; i < r; i++)
#define sper(i, r, l) for (register int i = r; i > l; i--)
#define maxn 200020
#define ll long long int 
using namespace std;

int n, k, s;
int ans[maxn], cs = 0;

int main(){
	
		//freopen("C.in", "r", stdin);
	
	cin >> n >> k >> s;
	rep(i, 1, k) printf("%d ", s);
	if (s > n - k) rep(i, 1, n - k) printf("1 ");
	else rep(i, 1, n - k) printf("1000000000 ");
	return 0;
}

Measured memory_bytes: 1280
import sys
import queue


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()


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

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

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int M = 101;

int H, W;
int sx, sy;
short ac[M][M];
string s[M];
short dp[M][M][M][M];

short get(int a, int b, int c, int d) { //[a,c],[b,d]
	if (a > c || b > d) return 0;
	return ac[c+1][d+1] - ac[c+1][b] - ac[a][d+1] + ac[a][b];
}

short calc(int p, int q, int r, int s) {//dead : bottom p, top r, right r, left s
	if (dp[p][q][r][s] != -1) {
		return dp[p][q][r][s];
	}
	short res = 0;

	if (p + r < H) {
		if (sx - p - 1 >= r) {
			res = max<short>(res, calc(p + 1, q, r, s) + get(sx - p - 1, max(sy - q, s), sx - p - 1, min(sy + s, W - 1 - q)));
		}
		if (sx + r + 1 < H - p) {
			res = max<short>(res, calc(p, q, r + 1, s) + get(sx + r + 1, max(sy - q, s), sx + r + 1, min(sy + s, W - 1 - q)));
		}
	}

	if (q + s < W) {
		if (sy - q - 1 >= s) {
			res = max<short>(res, calc(p, q + 1, r, s) + get(max(sx - p, r), sy - q - 1, min(sx + r, H - 1 - p), sy - q - 1));
		}
		if (sy + s + 1 < W - q) {
			res = max<short>(res, calc(p, q, r, s + 1) + get(max(sx - p, r), sy + s + 1, min(sx + r, H - 1 - p), sy + s + 1));
		}
	}

	return dp[p][q][r][s] = res;
}

int main() {
	cin >> H >> W;
	rep(i, H) cin >> s[i];
	rep(i, H) {
		rep(j, W) {
			ac[i+1][j+1] = ac[i+1][j] + ac[i][j+1] - ac[i][j] + (s[i][j] == 'o');
			if (s[i][j] == 'E') {
				sx = i, sy = j;
			}
		}
	}
	memset(dp, -1, sizeof(dp));

	cout << calc(0, 0, 0, 0) << endl;

	return 0;
}

Measured memory_bytes: 203648
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)     for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = m; i < (int)(n); i++)
#define MOD 1000000007
#define Graph vector<vector<int>>
#define lint int64_t

int main(){
    int N;
    cin >> N;
    
    vector<pair<string, int>> p(N);
    rep(i,N) {
      string si;
      int ti;
      cin >> si >> ti;
      p.at(i) = make_pair(si, ti);
    }
    
    bool flg = false;
    int ans = 0;
    string X;
    cin >> X;
    rep(i,N){
      string si;
      int ti;
      tie(si, ti) = p.at(i);
      if(flg) ans += ti;
      if(si == X) flg = true;
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import math
N,D = map(int, input().split())
kyori = 0
total = 0
for i in range(N): 
    X,Y = map(int, input().split())
    kyori = math.sqrt(X**2 + Y**2)
    if D >= kyori:
        total += 1
# 出力
print(total)

Measured memory_bytes: 9124
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main(){ 
  long long a,b,c,d,e=0;cin>>a>>b>>c>>d;
  e=a;
  if(a>=d){
    cout<<d;
  }
  else {d-=a;
  d-=b;
  if(d<=0){
    cout<<e;
  }
  else cout<<e-d;
  }
  }


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,k;
  cin >> a >> b>> c >> k;
  int xa=min(a,k);
  k-=xa;
  int xb=min(b,k);
  k-=xb;
  int xc=k;
  cout << xa-xc << endl;
  return 0;
}

Measured memory_bytes: 3588
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
typedef long long ll;
const int MAXN=1e5+5,MAXM=2e5+5,P=1e9+7;
 
int N,M,S,T;
 
struct E{int next,to,val;} e[MAXM<<1];int ecnt,G[MAXN];
void addEdge(int u,int v,int w){e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;}
void addEdge2(int u,int v,int w){addEdge(u,v,w);addEdge(v,u,w);}
 
ll fS[MAXN],dS[MAXN],fT[MAXN],dT[MAXN];
 
struct HN{int id;ll v;};
bool operator <(const HN &a,const HN &b){return a.v>b.v;}
std::priority_queue<HN> heap;
bool inS[MAXN];
void dijkstra(int v0,ll *f,ll *d)
{
	memset(inS,0,sizeof inS);
	memset(d,0x3f,sizeof dS);
	d[v0]=0,f[v0]=1;heap.push((HN){v0,0});
	while(!heap.empty())
	{
		int u=heap.top().id;heap.pop();
		if(inS[u]) continue;inS[u]=true;
		for(int i=G[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(inS[v]) continue;
			if(d[v]>d[u]+e[i].val)
			{
				f[v]=f[u];
				d[v]=d[u]+e[i].val;
				heap.push((HN){v,d[v]});
			}
			else if(d[v]==d[u]+e[i].val) f[v]=(f[v]+f[u])%P;
		}
	}
}
 
struct A{int u,v,w;} a[MAXM];
int main()
{
	int i;scanf("%d%d%d%d",&N,&M,&S,&T);
	for(i=1;i<=M;i++)
	{
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		addEdge2(u,v,w);a[i]=(A){u,v,w};
	}
	dijkstra(S,fS,dS);
	dijkstra(T,fT,dT);
	int ans=(ll)fS[T]*fS[T]%P;
	for(i=1;i<=N;i++)
		if(dS[i]==dT[i]&&dS[i]+dT[i]==dS[T])
			ans=(ans+P-fS[i]*fS[i]%P*fT[i]%P*fT[i]%P)%P;
	for(i=1;i<=M;i++)
	{
		int u=a[i].u,v=a[i].v,w=a[i].w;
		if(dS[u]>dS[v]) std::swap(u,v);
		if(dS[u]<dS[T]>>1&&dT[v]<dT[S]>>1&&dS[u]+dT[v]+w==dS[T])
		//if(dS[u]+dT[v]+w==dS[T]&&std::max(dS[u],dT[v])<std::min(dS[u],dT[v])+w)
			ans=(ans+P-fS[u]*fS[u]%P*fT[v]%P*fT[v]%P)%P;
	}
	printf("%d",ans);
	return 0;
}

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

mx = sum(A)

count_a = 0
count_b = 0
a_Flag = False
b_Flag = False
for i in range(len(A)):
    if not a_Flag:
        count_a += A[i]
    if not b_Flag:
        count_b += A[N - i - 1]
    if mx / 2 <= count_a:
        a_Flag = True
    if mx / 2 <= count_b:
        b_Flag = True
    if a_Flag and b_Flag:
        break

other_a = mx - count_a
other_b = mx - count_b
if count_a - other_a < count_b - other_b:
    print(abs(count_a - other_a))
else:
    print(abs(count_b - other_b))

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

void pri(int n, vector<int> &v) {
    for(int i=0;i<n;i++) {
        if(i) cout << " ";
        cout << v[i];
    }
    cout << "\n";
}

void insertion_sort(int n, vector<int> &v) {
    for(int i=0;i<n;i++) {
        for(int j=i-1;j>=0;j--) {
            if(v[j] > v[j+1])swap(v[j+1],v[j]);
        }
        pri(n,v);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0;i<n;i++)cin >> v[i];
    insertion_sort(n,v);

    return 0;
}




Measured memory_bytes: 3100
package main

import "fmt"

func main() {
	//
	var N int
	var S string

	fmt.Scanf("%d", &N)
	fmt.Scanf("%v", &S)


	num := 0
	l := len(S)

	// Sから3文字残す。パターンは何通りあるか。
	// 010203298
	// 3文字なので、最初の文字は00-99の99通り。
	// 2文字を最速で見つけ最後の文字が取り売るのはなにか、を見つける。
	// 003
	for i := 0; i <= 99; i++ {
		two := fmt.Sprintf("%02d", i)
		// 1文字目を探す
		k := 0
		for k = 0; k < l; k++ {
			if S[k] == two[0] {
				k++
				break
			}
		}
		if k == l {
			continue
		}
		// 2文字目を探す
		for ; k < l; k++ {
			if S[k] == two[1] {
				k++
				break
			}
		}
		if k == l {
			continue
		}
		//fmt.Printf("try to find 3rd\n")
		// 3文字目を探す
		n := 0
		var found [10]bool
		for ; k < l; k++ {
			d := S[k] - '0'
			if found[d] == false {
				found[d] = true
				n++
				if n == 10 {
					break
				}
			}
		}
		num += n
	}

	fmt.Printf("%d\n", num)
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
typedef long long ll;
//typedef vector<ll> vec;
//typedef vector<vec> mat;

int N,M,H,W,K,A,B;
string S;
string alpha = "abcdefghijklmnopqrstuvwxyz";
string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

const int MAX_N = 301;
typedef vector<double> vec;
typedef vector<vec> mat;
typedef vector<mat> R3;
R3 dp(MAX_N,mat(MAX_N,vec(MAX_N,-1)));

double E(int a,int b, int c){
    if(a==0&&b==0&&c==0) return 0;
    if(dp[a][b][c]!=-1) return dp[a][b][c];
    double ans = N;
    if(a != 0) ans += a*E(a-1,b,c);
    if(b != 0) ans += b*E(a+1,b-1,c);
    if(c != 0) ans += c*E(a,b+1,c-1);
    ans /= a+b+c;
    dp[a][b][c] = ans;
    return ans;
}

int main() {
    cin>>N;
    int fa,fb,fc;
    fa=fb=fc=0;
    rep(i,N){
        cin>>M;
        if(M==1)++fa;
        if(M==2)++fb;
        if(M==3)++fc;
    }
    cout<<fixed<<setprecision(11)<<E(fa,fb,fc)<<endl;
}

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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

string s;

int main(){
	cin.sync_with_stdio(false);
  cin>>s;
  cout<<(s[0]==s[2]?"Yes":"No")<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

typedef struct Edge {
    ll to, cost;
} Edge;

vector<vector<Edge>> g;
vector<bool> vi;
int k, num;

void dijkstra(vector<ll> &d, int s) {
    priority_queue<P, vector<P>, greater<P>> pq;
    d[s] = 0;
    // P<dist, v>
    pq.push({0,s});

    while (!pq.empty()) {
        P p = pq.top(); pq.pop();
        int v = p.second;

        for(auto &&e: g[v]) {
            if (d[e.to] > d[v]+e.cost) {
                d[e.to] = d[v]+e.cost;
                pq.push({d[e.to], e.to});
            }
        }
    }
}

void dfs(vector<P> &b, int x, int dist) {
    if (vi[x]) return;
    vi[x] = true;
    for (auto &&e: g[x]) {
        b[x] = {num,dist};
        dfs(b, e.to, dist+1);
        if (k == x) ++num;
    }
}


int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    g.resize(n);
    REP(i,n-1) {
        ll a,b,c;
        cin >> a >> b >> c;
        --a, --b;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    int q;
    cin >> q >> k;
    --k;
    vi.resize(n, false);

    vector<ll> d(n, LINF);
    vector<P> branch(n);
    dijkstra(d, k);
    dfs(branch, k, 0);

    REP(i,q) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        ll ans = 0;
        ans = d[x]+d[y];
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 18944
//Author: Pakhomovee 
#include <iostream> 
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <deque>
#include <assert.h>

using namespace std;
using namespace std::chrono;

void solve()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	vector<vector<int>> lol(1000001);
	for (int i = 0; i < n; ++i)
	{
		lol[a[i]].push_back(i);
	}
	vector<int> cnt(n, 0);
	set<int> s;
	for (int i : a)
	{
		s.insert(i);
	}
	for (int i = 0; i < n; ++i)
	{
		if (s.count(a[i]))
		{
			s.erase(a[i]);
			for (int j = 1; j * a[i] <= 1000000; ++j)
			{
				for (int k : lol[j * a[i]])
				{
					if (k != i)
					{
						++cnt[k];
					}
				}
			}
		}
	}
	int ans = 0;	
	for (int i = 0; i < n; ++i)
	{
		if (cnt[i] == 0 && lol[a[i]].size() == 1)
		{
			++ans;
		}
	}
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	auto start = system_clock::now();

	solve();

	auto end = system_clock::now();
	cerr << "Time: " << duration_cast<milliseconds> (end - start).count() << "ms" << endl;
}

Measured memory_bytes: 43876
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
#include <numeric>
using namespace std;
typedef long long int ll;

ll mod=1e9+7;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<pair<int,int> > v;
	for(int i=0;i<n;i++){
		int a; cin >> a;
		v.push_back(make_pair(a,0));
	}
	for(int i=0;i<n;i++){
		int a; cin >> a;
		v.push_back(make_pair(a,1));
	}
	sort(v.begin(),v.end());
	ll ans=1;
	ll aleft=0;
	ll bleft=0;
	for(auto p:v){
		if(p.second==0){
			if(bleft){
				ans*=bleft;
				ans%=mod;
				bleft--;
			}
			else{
				aleft++;
			}
		}
		else{
			if(aleft){
				ans*=aleft;
				ans%=mod;
				aleft--;
			}
			else{
				bleft++;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 2420