akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m ;
	cin >> n >> m;
	vector<vector<int>>graph(n+1, vector<int>(0));
	graph.at(0) = { 1 };
	graph.at(1) = { 0 };
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		graph.at(x).push_back(y);
		graph.at(y).push_back(x);
	}
	vector<int>ans(n+1,-1);
	ans.at(0) = 0;
	ans.at(1) = 0;
	queue<int>search;
	search.push(1);
	while (search.size() > 0) {
		int a = search.front();
		//cout << ans.at(0) << ans.at(1) << ans.at(2) << ans.at(3) << ans.at(4) << endl;
		vector<int> b = graph.at(a);
		//cout << b.size() << endl;
		for (int i = 0; i < b.size(); i++) {
			if (ans.at(b.at(i)) == -1) {
				ans.at(b.at(i)) = a;
				search.push(b.at(i));
			}
		}
		search.pop();
	}
	cout << "Yes" << endl;
	for (int i = 2; i <= n; i++)cout << ans.at(i) << endl;
}

Measured memory_bytes: 10524
#include<iostream>
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
using namespace std;
int main()
{
    fastio;
    long long n,i,cnt=0;
    cin>>n;
    long long a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]%2==1)
        {
            cnt++;
        }
    }
    if(cnt%2==0)
    {
        cout<<"YES";
    }
    else
    {
        cout<<"NO";
    }
}

Measured memory_bytes: 4316
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long a = sc.nextInt();
		long b = sc.nextInt();
		long[] x = new long[n];
		long dist = 0;
		long ans = 0;
		for(int i=0; i<n; i++){
			x[i] = sc.nextInt();
		}

		for(int i=0; i<n-1; i++){
			dist = x[i+1] - x[i];
			if(dist * a < b){
				ans += dist * a;
			}else{
				ans += b;
			}
		}
		System.out.println(ans);
		return;
	}
}

Measured memory_bytes: 34708
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
    int n;
    string s;
    cin >> n >> s;
    for(int i=0; i<s.size(); i++){
        s[i]+=n;
        if(s[i]>='[')s[i]-=26;
        cout << s[i];
    }
    cout << endl;
}

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

n, k = map(int, input().split())
have = [0] * (n + 1)
for i in range(k):
	d = int(input())
	a = list(map(int, input().split()))
	for x in a:
		have[x] += 1
res = 0
for i in range(1, n + 1):
	if have[i] == 0:
		res +=1 
print(res)

Measured memory_bytes: 67336
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n;
int a[200001],b[200001];
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	rep(i,n){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b,b+n);
	rep(i,n)
	if(a[i]<b[n/2])
	cout<<b[n/2]<<"\n";
	else
	cout<<b[n/2-1]<<"\n";	
	re 0;
}


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

int main()
{
    int n;cin>>n;
    vector<int> a(n);
    int i;
    for(i=0;i<n;i++)cin>>a.at(i);
    if(n%2==0)
    {
        for(i=0;i<n/2;i++)
        {
            if(i==0)cout<<a.at(n-1);
            else cout<<' '<<a.at(n-1-i*2);
        }    
        for(i=0;i<n/2;i++)
        {
            cout<<' '<<a.at(i*2);
        }
    }
    else
    {
        for(i=0;i<n/2+1;i++)
        {
            if(i==0)cout<<a.at(n-1);
            else cout<<' '<<a.at(n-1-i*2);
        }
        for(i=0;i<n/2;i++)
        {
            cout<<' '<<a.at(i*2+1);
        }
    }
    cout<<endl;
}


Measured memory_bytes: 3072
#include<bits/stdc++.h>;
#define rep(i,n) for(int i = 0 ; i < n; i++)
using namespace std;
int main(){
  int inp;
  int flag=0;
  cin>>inp;
  if(inp%10==7)flag=1;
  if(floor((inp%100)/10)==7)flag=1;
  if(floor(inp/100)==7) flag=1;
  if(flag) cout<<"Yes";
  else cout<<"No";
  return 0;
}
  


Measured memory_bytes: 3592
m,d = map(int, input().split())

ans = 0
for month in range(4, m+1):
  for day in range(22, d+1):
    sday = str(day)
    if int(sday[1]) < 2:
      continue
    if int(sday[0]) * int(sday[1]) == month:
      ans += 1

print(ans)

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

using namespace std;

int main()
{
    long long int n,arr[205],sum;

    while(scanf("%lld",&n)==1)
    {
        for(int i=0; i<(n*2); i++)
        {
            scanf("%lld",&arr[i]);
        }

        sort(arr, arr+(n*2));

        sum=0;

        for(int i=0; i<(n*2); i++)
        {
            if(i%2==0)
            {
                sum+=arr[i];
            }
        }

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

    return (0);
}


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


int main(){
  int h,w;
  cin>>h>>w;
  vector<vector<int>> a(h,vector<int>(w));
  rep(i,h)rep(j,w) cin>>a[i][j];
  
  vector<vector<int>> d(h,vector<int>(w));
  int res=0;
  rep(i,h-1){
    rep(j,w){
      if(a[i][j]%2==0) continue;
      d[i][j]=1;
      res++;
      a[i][j]--;
      a[i+1][j]++;
    }
  }
  rep(j,w-1){
    if(a[h-1][j]%2==0) continue;
    d[h-1][j]=1;
    res++;
    a[h-1][j]--; 
    a[h-1][j+1]++;
  }
  
  cout<<res<<endl;
  rep(i,h-1)rep(j,w){
    if(d[i][j]==1){
      cout<<i+1<<" "<<j+1<<" "<<i+2<<" "<<j+1<<endl;
    }
  }
  rep(j,w){
    if(d[h-1][j]==1){
      cout<<h<<" "<<j+1<<" "<<h<<" "<<j+2<<endl;
    }
  }
}
  

Measured memory_bytes: 4096
#include<iostream>

int main()
{
    long long N, M;
    
    std::cin >> N >> M;
    
    if((M==2)||(N==2))
        N=0;
    if(N-2>0){
        N-=2;
    }
    if(M-2>0)
        M-=2;
    
    std::cout << (N*M) << std::endl;
    return 0;
}




Measured memory_bytes: 256
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 50010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=spf[1] = -1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD

def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''

def chk(s):
    return s==s[::-1]
s = input()
n = len(s)
x = s[:(n-1)//2]
y = s[(n+3)//2-1:]

if chk(s) and chk(y) and chk(x):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 7188
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] lines = sc.next().split(",");
            double[] l = new double[6];
            for (int i = 0; i < 6; i++) {
                l[i] = Double.parseDouble(lines[i]);
            }
            double x, y, d, e;
            if (l[0] == l[2]) {
                y = l[5];
                x = 2 * l[0] - l[4];
            } else if (l[1] == l[3]) {
                x = l[4];
                y = 2 * l[1] - l[5];
            } else {
                d = (l[3] - l[1]) / (l[2] - l[0]);
                e = l[1] - d * l[0];
                x = (2 * l[5] * d - 2 * d * e + l[4] - d * d * l[4]) / (d * d + 1);
                y = (l[4] - x) / d + l[5];
            }
            System.out.println(x + " " + y);
        }
    }
}


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

void printList(int num[], int n){
	for (int i = 0; i < n; i++){
		cout << num[i];
		if (i != n-1) cout << ' ';
	}
	cout << endl;
}

void swap(int *x, int *y){
	int tmp;
	tmp = *x;
	*x = *y;
	*y = tmp;
}

int selectionSort(int num[], int n){
	int min, j, count = 0;
	for (int i = 0; i < n; i++){
		min = i;
		for (j = i; j < n; j++){
			if (num[min] > num[j])
				min = j;
		}
		if (min != i){
			swap (num[min], num[i]);
			count++;
		}
	}
	return count;
}

int main(){
	int n[100];
	int limit;
	cin >> limit;
	for (int i = 0; i < limit; i++){
		cin >> n[i];
	}
//	printList(n, limit);
	int count;
	count = selectionSort(n, limit);
	printList(n, limit);
	cout << count << endl;
	return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a;
  cin >> a;
  int num = 0;
  while (a > 0) {
    int b ,c;
    cin >> b >> c;
    num += (c - b + 1);
    a--;
  }
  cout << num << endl;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> p(N);
    int cnt = 0;
    for(int i = 0; i < N; i++){
        cin >> p[i];
        if(p[i] != i + 1){
            cnt++;
        }
    }
    cout << (cnt > 2 ? "NO": "YES") << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<map>
#include <algorithm>
#include<cstdlib>
#include<cmath>
#include<deque>
#include <numeric>
typedef  long long ll;

int main() {
	ll k, a, b;
	std::cin >> k >> a >> b;

	b-=a;
	ll ans = 1;
	if (b <= 2) std::cout << k + 1 << '\n';
	else {
		ll tmp = std::min(k, a-1);
		ans += tmp;
		k -= tmp;
		if (k%2) ans++, k--;
		ans += k/2 *(b);
		std::cout << ans << '\n';
	}
	return 0;
}

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

int T, N, K, X[100000+10], A[100000+10];
int main() {
   cin >> T;
   for (int t=0; t<T; t++) {
     cin >> N >> K;

     for (int i=0; i<N; i++) cin >> X[i];

     if (N <= K) {
       cout << 0 << endl;
       continue;
     } else {

       for (int i=0; i+1<N; i++) A[i] = X[i+1] - X[i];
       sort(A, A+N-1);
      //  for (int i=0; i+1<N; i++) cout << "." << A[i] << endl; 


       int answer = 0;
       int road = max(0, N-1-(K-1));

       for (int i=0; i<road; i++) {
         answer += A[i];
        //  cout << "+" << A[i] << endl;
       }
       cout << answer << endl;

     } 
     
   }
  }


Measured memory_bytes: 3828
#include <iostream>
#include <cstdio>
#include <cctype>

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

const int N=100005;

int gcd(int x,int y){return y?gcd(y,x%y):x;}

int a[N];
int n;
bool ok,res;

int main()
{
	//freopen("decrementing.in","r",stdin),freopen("decrementing.out","w",stdout);
	n=read(),ok=0;
	for (int i=1;i<=n;++i) a[i]=read();
	for (bool cur=0;!ok;cur^=1)
	{
		bool par=0,one=0;
		int even=0,odd=0;
		for (int i=1;i<=n;++i) par^=(a[i]-1)&1,one|=a[i]==1,odd+=a[i]&1;
		even=n-odd,ok=1;
		if (one) res=par^cur;
		else if (even&1) res=!cur;
		else if (odd>=2) res=cur;
		else
		{
			for (int i=1;i<=n;++i) if (a[i]&1) --a[i];
			int g=a[1];
			for (int i=2;i<=n;++i) g=gcd(g,a[i]);
			for (int i=1;i<=n;++i) a[i]/=g;
			ok=0;
		}
	}
	printf("%s\n",res?"First":"Second");
	//fclose(stdin),fclose(stdout);
	return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main {

    public static void main(String[] args) {

        int n, l;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        l = sc.nextInt();

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += l + i - 1;
        }

        if(l >= 0){
            ans -= l;
        } else if (l + n - 1 <= 0){
            ans -= l + n - 1;
        }
        System.out.println(ans);
        return;
    }
}


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

int main() {
  int N,Y;
  cin >> N >> Y;
  int a=-1,b=-1,c=-1;
  for(int x=0;x<=N;x++){
    for(int y=0;x+y<=N;y++){
      int z=N-x-y;
      int sum=10000*x + 5000*y + 1000*z;
      if(sum==Y){
        a=x;
        b=y;
        c=z;
      }
    }
  }
  cout << a << " " << b << " " << c << endl;     
}

Measured memory_bytes: 256
program main
	implicit none
    integer::a,b,k,i
    read(*,*)k
    read(*,*)a,b
    do i=a,b
    	if(mod(i,k)==0)then
        	write(*,*) 'OK'
            stop
        end if
    end do
    write(*,*)'NG'
    stop
end program main

Measured memory_bytes: 2856
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;
long long int INF = 1e18;
int DP[1100][1100] = {};


int main()
{
	string str1, str2;
	cin >> str1 >> str2;
	
	for(int i = 0; i <= str1.size(); i++){
		DP[i][0] = i;
	}
	
	for(int i = 0; i <= str2.size(); i++){
		DP[0][i] = i;
	}
	
	for(int i = 1; i <= str1.size(); i++){
		for(int j = 1; j <= str2.size(); j++){
			DP[i][j] = min(DP[i - 1][j] + 1, DP[i][j - 1] + 1);
			if(str1[i - 1] == str2[j - 1]){
				DP[i][j] = min(DP[i][j], DP[i - 1][j - 1]);
			}else{
				DP[i][j] = min(DP[i][j], DP[i - 1][j - 1] + 1);
			}
		}
	}
	/*
	for(int i = 0; i <= str1.size(); i++){
		for(int j = 0; j <= str2.size(); j++){
			cout << DP[i][j] << " ";
		}
		cout << endl;
	}
	*/
	cout << DP[str1.size()][str2.size()] << endl;
	
	return 0;
}


Measured memory_bytes: 7500
N=int(input())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
count=0
for i in range(N):
    if i==0:
        now=0
        nex=A[0]
        count+=1
    else:
        
        nex=A[nex-1]
        count+=1
    if nex==2:
        print(count)
        exit()

print(-1)

Measured memory_bytes: 7084
/**
 *      ABC 111 C
 *      author  : kyomukyomupurin
 *      created : 2018-09-29 21:04:31
**/

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    int v[n + 3] = {};
    for (auto i = 0; i < n; ++i) {
        cin >> v[i];
    }

    int countEven[100000] = {};
    int countOdd[100000] = {};

    for (auto i = 0; i < n ; i += 2) {
        ++countEven[v[i]];
    }

    for (auto i = 1; i < n; i += 2) {
        ++countOdd[v[i]];
    }

    auto maxEven = max_element(countEven, countEven + 100000);
    auto maxOdd = max_element(countOdd, countOdd + 100000);

    int maxNeven = distance(countEven, maxEven);    // 最頻値
    int maxNodd = distance(countOdd, maxOdd);

    int secondEven[100000] = {}; int secondOdd[100000] = {};

    for (auto i = 0; i < n; i += 2) {
        if (v[i] != maxNeven){
            ++secondEven[v[i]];
        }
    }

    for (auto i = 1; i < n; i += 2) {
        if (v[i] != maxNodd){
            ++secondOdd[v[i]];
        }
    }

    int evenSecond = *max_element(secondEven, secondEven + 100000);
    int oddSecond = *max_element(secondOdd, secondOdd + 100000);

    if (maxNeven == maxNodd){
        if (evenSecond >= oddSecond){
            cout << n / 2 - evenSecond + n / 2 - *max_element(countOdd, countOdd + 100000) << endl;
        }
        else {
            cout << n / 2 -  oddSecond + n / 2 - *max_element(countEven, countEven + 100000) << endl;
        }
    }
    else {
        cout << n - (*max_element(countEven, countEven + 100000) + *max_element(countOdd, countOdd + 100000)) << endl;
    }
    
    return 0;
}

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


int main()
{
	int n, d; cin >> n >> d;
	int X[n][d];
	for (int i = 0; i < n; ++i)
		for(int j = 0; j < d; ++j)
			cin >> X[i][j];

	int c = 0;
	for (int i = 0; i < n; ++i)
		for(int j = i+1; j < n; ++j)
		{
			double y = 0;
			for (int k = 0; k < d; ++k)
			{
				double x = X[i][k] - X[j][k];
				y += x*x;
			}
			y = sqrt(y);
			if (y - int(y) == 0) c++;
		}
	cout << c << endl;
}


Measured memory_bytes: 3616
fun main(args: Array<String>) {
    val (s, t) = readStringList()
    val (a, b) = readIntegerList()
    val u = readLine()!!
    if (s == u) {
        println("${a - 1} $b")
    } else {
        println("$a ${b - 1}")
    }
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)


Measured memory_bytes: 36008
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;
using P = std::pair<ll, ll>;

constexpr ll INF = 1ll<<60;

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

template<class S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

using PP = std::pair<P, ll>;

ll N, M, L;
std::vector<std::vector<P>> G;
ll Q;
P dist[310][310];

void dijkstra( ll s, std::vector<std::vector<P>> &G )
{
  std::priority_queue<PP, std::vector<PP>, std::greater<PP>> pque;

  rep( t, N )
    dist[s][t] = P( INF, INF );

  dist[s][s] = P( 0, 0 );

  pque.emplace( P( 0, 0 ), s );

  while( !pque.empty() )
  {
    PP p = pque.top(); pque.pop();
    ll cnt = p.first.first, dC = p.first.second, v = p.second;

    if( p.first > dist[s][v] )
      continue;

    //std::cout << p.first << ", " << v  << std::endl;

    for( auto u : G[v] )
    {
      bool upd = false;
      ll ndC = dC+u.second;

      if( L-dC < u.second )
      {
        ndC = u.second;
        upd = true;
      }

      if( chmin( dist[s][u.first], P( cnt+upd, ndC ) ) )
        pque.emplace( dist[s][u.first], u.first );
    }
  }

  return;
}

int main()
{
  std::cin >> N >> M >> L;

  G.assign( N+10, std::vector<P>() );

  rep( i, M )
  {
    ll A, B, C;
    std::cin >> A >> B >> C;
    --A; --B;

    if( C <= L )
    {
      G[A].emplace_back( B, C );
      G[B].emplace_back( A, C );
    }
  }

  rep( s, N )
    dijkstra( s, G );

  std::cin >> Q;

  rep( i, Q )
  {
    ll s, t;
    std::cin >> s >> t;
    --s; --t;

    std::cout << (dist[s][t].first==INF ? -1 : dist[s][t].first) << std::endl;
  }

  return 0;
}

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

int main() {
    int  N;
    cin >> N;
    int64_t ttl=0;
    for (int i = 1; i <=N; i++)
    {
        if(i%3==0) continue;
        if(i%5==0) continue;
        else ttl+=i;
    }
    cout << ttl << endl;
}



Measured memory_bytes: 3596
#include <algorithm>
// #include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double db;
const int oo=2139063143;
const int N=17;
const int P=1000000007;
const db eps=1e-7;
#define pritnf printf
//char buf[1<<22],*p1=buf,*p2=buf,obuf[1<<22],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T>
inline void sc (T &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
template <typename T>
inline void print (T x)
{
    if (x< 0) putchar('-'),x=-x;
    if (x>=10) print(x/10);
    putchar(x%10+'0');
}
template <typename T>
inline void pr (T x) { print(x),putchar('\n'); }
template <typename T1,typename T2>
void chkmax (T1 &A,T2 B) { A=A>=B?A:B; }
template <typename T1,typename T2>
void chkmin (T1 &A,T2 B) { A=A<=B?A:B; }
int n,m,e[N][N],e0=0,g[1<<N|1],f[1<<N|1][N];

int main ()
{
    // freopen (".in","r",stdin);
    // freopen (".out","w",stdout);
	sc(n),sc(m);
	for (int i=1; i<=m; i++)
	{
		int x,y; sc(x),sc(y),sc(e[x][y]),e[y][x]=e[x][y];
		e0+=e[x][y];
	}
	int S=(1<<n)-1;
	for (int s=1; s<=S; s++)
		for (int i=1; i<=n; i++) if (s>>(i-1)&1)
			for (int j=i; j<=n; j++) if (s>>(j-1)&1)
				g[s]+=e[i][j];
	for (int s=0; s<=S; s++)
		for (int i=0; i<=n; i++)
			f[s][i]=-2e9;
	f[1][1]=0;
	for (int s=1; s< S; s++)
		for (int u=1; u<=n; u++) if (s>>(u-1)&1)
		{
			for (int v=1; v<=n; v++) if (!(s>>(v-1)&1)&&e[u][v])
				chkmax (f[s|(1<<(v-1))][v],f[s][u]+e[u][v]);
			int ss=S^s;
			for (int t=ss; t; t=(t-1)&ss)
				chkmax (f[s|t][u],f[s][u]+g[t|(1<<(u-1))]);
		}
	pr(e0-f[S][n]);

    return 0;
}


Measured memory_bytes: 4352
def two_dim_merge_sort(arr):##arrは二次元配列
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = two_dim_merge_sort(left)
    right = two_dim_merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return two_dim_merge(left, right)


def two_dim_merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i][0] <= right[r_i][0]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged



n, k = map(int,input().split())

a = [0] * n
b = [0] * n

for i in range(0,n):
    a[i], b[i] = map(int,input().split())

l = [0] * n

for i in range(0,n):
    l[i] = [a[i],b[i]]

ll = two_dim_merge_sort(l)

s = 0

for i in range(0,n):
    s = s + ll[i][1]
    if s >= k:
        ans = ll[i][0]
        break

print(ans)

Measured memory_bytes: 23636
use std::io;
use std::str::FromStr;
fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut it = input.split_whitespace().map(|x| i32::from_str(x).unwrap());
    let (mut h, n) = (it.next().unwrap(), it.next().unwrap());
    let mut ans = 0;
    {
        let mut done = false;
        while !done {
            ans += 1;
            h -= n;
            if h <= 0 {
                done = true;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;




int main()
{
   
    int N;
    cin >> N;
    string S;
    cin >> S;
    string ans = "";
    
    int a = 0, b = 0;
    
    for (int i = 0; i < N; i++) {
        if(S[i] == ')'){
            if(b > 0) b--;
            else a++;
        }else{
            b++;
        }
        
    }
    
    rep(i,a) ans += "(";
    ans += S;
    rep(i,b) ans += ")";
    
    
    cout << ans << endl;
    
    
    
    return 0;
}



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

signed main(){
  int R[26];
  rep(i,26) R[i]=0;
  string s,ans="Yes";
  cin>>s;
  rep(i,s.size())R[s[i]-'a']+=1;
  rep(i,26){
    if(R[i]%2==1)ans="No";
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var B = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        var sum = B.First();
        for (int i = 0; i < n - 2; i++)
        {
            sum += Math.Min(B[i], B[i + 1]);
        }
        sum += B.Last();

        Console.WriteLine(sum);
    }
}

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

int main()
{
	int a,b,c,x;
	x = 0;
	cin >> a >> b >> c;	
	for (a; a <= b; a++) {
		if (c % a == 0) {
			x++;
		}
	}
	cout << x << endl;
	return 0;
}

Measured memory_bytes: 3084
#include <stdio.h>

int main(void)
{
	int i, j, howmanycards, card_num, card_suit;
	int cards[4][14];
	char suit; 

	for(i=0; i < 4; i++)
	{
		for(j=0; j < 14; j++)
		{
			cards[i][j] = 0;
		}
	}

	scanf("%d", &howmanycards);
	for(i = 0; i < howmanycards; i++)
	{
		scanf(" %c %d", &suit, &card_num);
		switch(suit)
		{
			case 'S':
				card_suit = 0;
				break;
			case 'H':
				card_suit = 1;
				break;
			case 'C':
				card_suit = 2;
				break;
			case 'D':
				card_suit = 3;
		}
		cards[card_suit][card_num] = 1;
	}

	for(i = 0; i < 4; i++)
	{
		for(j = 1; j < 14; j++)
		{
			if(cards[i][j] == 0)
			{
				switch(i)
				{
					case 0:
						printf("S ");
						break;
					case 1:
						printf("H ");
						break;
					case 2:
						printf("C ");
						break;
					case 3:
						printf("D ");
						break;
				}
				printf("%d\n", j);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 596
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
sa=[0]*(N+1)
sb=[0]*(M+1)
for i in range(N):
    sa[i+1]=sa[i]+A[i]
for i in range(M):
    sb[i+1]=sb[i]+B[i]
ans=0
for i in range(N+1):
    if sa[i]<=K:
        res=bisect_right(sb,K-sa[i])
        tmp=i+res-1
        ans=max(ans,tmp)
print(ans)

Measured memory_bytes: 116728
#include<bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define zero(v) memset(v,0,sizeof(v))
#define rep(i,n) for(int i=0;i<(n);i++)
#define foreach(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define all(v) (v).begin(),(v).end()
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
typedef long long ll;
typedef unsigned uint;
const int INF=0x3f3f3f3f;
const double EPS=1e-10;
typedef pair<int,int> pii;
int inline in(){int x=0,c;for(;(uint)((c=getchar())-'0')>=10;)
{if(c=='-')return -in();if(!~c)throw ~0;}do{x=(x<<3)+(x<<1)+(c-'0');}
while((uint)((c=getchar())-'0')<10);return x;}
int n,m,k;
const int Maxn=3e5+5;
pii point[Maxn];

int cntR[Maxn];

inline bool cmp(const pii &a,const pii &b){
	return a.second<b.second;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<k;i++){
		scanf("%d%d",&point[i].first,&point[i].second);
		point[i].first--;
		point[i].second--;
		cntR[point[i].first]++;
	}
	sort(point,point+k,cmp);
	
	set<pii>ss;
	for(int i=0;i<n;i++){
		ss.insert(make_pair(-cntR[i],i));
	}
	
	int ans=0,cur=0;
	vector<int>v;
	for(int j=0;j<m;j++){
		int tmp=0;
		v.clear();
		while(cur<k&&point[cur].second==j){
			v.push_back(cur);
			tmp++;
			ss.erase(make_pair(-cntR[point[cur].first],point[cur].first));
			cntR[point[cur].first]--;
			ss.insert(make_pair(-cntR[point[cur].first],point[cur].first));
			cur++;
		}
		chkmax(ans,tmp-ss.begin()->first);
		for(int i=0;i<SZ(v);i++){
			int id=v[i];
			ss.erase(make_pair(-cntR[point[id].first],point[id].first));
			cntR[point[id].first]++;
			ss.insert(make_pair(-cntR[point[id].first],point[id].first));
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 22844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(i=0;i<n;i++)
int main(){
    int n,T; cin>>n>>T;
    int ans=0; 
    int i;
    int t[n]; rep(i,n)cin>>t[i];
    rep(i,n-1){
      ans+=min(T,t[i+1]-t[i]);
    }
    ans+=T;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
using namespace std;

#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 iREP(i,Itr) for(auto (i)=(Itr).begin();(i)!=(Itr).end();(i)++)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
#define PB_VEC(Itr1,Itr2) (Itr1).insert((Itr1).end(),(Itr2).begin(),(Itr2).end())
#define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end())
#define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val))
#define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val))
typedef long long ll;

int main(){
    
    int N;
    cin>>N;
    vector<int> a(N);
    REP(i,N)cin>>a[i];
    
    map<int,int> vertex;
    REP(i,a.size()){
        if(vertex.find(a[i])!=vertex.end())vertex[a[i]]++;
        else vertex[a[i]]=1;
    }
    
    vector< pair<int,int> > vs;
    iREP(i,vertex)vs.push_back(make_pair(i->first,i->second));
    reverse(vs.begin(),vs.end());
    
    int maxs=vs[0].first;
    int mins=vs[vs.size()-1].first;
    
    if(maxs%2==0){
        if(vertex[mins]!=1){
            cout<<"Impossible"<<endl;
            return 0;
        }
    }else{
        if(vertex[mins]!=2){
            cout<<"Impossible"<<endl;
            return 0;
        }
    }
    
    for(int i=maxs;i>=maxs/2+1;i--){
        if(vertex.find(i)==vertex.end()){
            cout<<"Impossible"<<endl;
            return 0;
        }else{
            if(vertex[i]<2){
                cout<<"Impossible"<<endl;
                return 0;
            }
        }
    }
    
    cout<<"Possible"<<endl;
    
    return 0;
}

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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define SORTG(v) sort(v.begin(),v.end(),greater<>())
#define SORT(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/3

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<string> Vs;

template<class T> void chmax(T& a, T b) {if(a<b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a>b){a=b;}}
void YesNo(int a){cout<<((a)?"Yes":"No")<<endl;}
void YESNO(int a){cout<<((a)?"YES":"NO")<<endl;}
void AorB(int a,string b,string c){cout<<((a)?b:c)<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void start(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);}

bool pairCompare(const Pii& firstElof, const Pii& secondElof)
{
    return firstElof.first > secondElof.first;
}

signed main(){start();
    int n,m;
    cin>>n>>m;
    Vi a(n),b(m),c(m);
    vector<Pii> d(m);
    REP(i,0,n) cin>>a[i];
    REP(i,0,m){
        cin>>b[i]>>c[i];
        d[i]=mp(c[i],b[i]);
    }
    SORT(a);
    sort(d.begin(), d.end(), pairCompare);
    int now=0;
    REP(i,0,m){
        if(d[i].first<=a[now]) break;
        REP(j,0,d[i].second){
            if(d[i].first>a[now]) a[now]=d[i].first;
            now++;
            if(now>=a.size()) goto out;
        }
    }
out:
    int ans=0;
    REP(i,0,n) ans+=a[i];
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 4224
#include <stdio.h>
int main(void) {
  int v,d[256],n=0;
  while(scanf("%d",&v)!=EOF){
    if(v) {
      d[n]=v;
      n++;
    } else {
      n--;
      printf("%d\n",d[n]);
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;
  int sum_digits = 0;
  int t = n;
  while (t) {
    sum_digits += t % 10;
    t /= 10;
  }
  if (n % sum_digits)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  
  int arr[N]={0};
  for(int i=1;i<=100;i++){
    for(int j=1;j<=100;j++){
      for(int k=1;k<=100;k++){
        int n=i*i+j*j+k*k+i*j+i*k+j*k;
        if(n<=N){
          arr[n-1]++;
        }
      }
    }
  }
  for(int i=0;i<N;i++){
    cout<<arr[i]<<endl;
  }
  return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector> 
#include <cmath>
using namespace std;

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

	
	char first = t[0];
	char second = t[1];
	char third = t[2];
	
	if (first == second && second == third){
		cout << "No";
		return 0;
	}
	else cout << "Yes";	
	
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define sort(a) sort(all(a))
using P = pair<int, int>;
using ll = long long;
using ld = long double;
typedef vector<int> vi;
int dx[4] = { 0, 1, 0,-1 };
int dy[4] = { 1, 0,-1, 0 };
const ll MOD = 1000000007;

signed main() {
  int N, L;
  cin >> N >> L;
  vi A;
  rep(i, N) {
    A.push_back(L+i);
  }
  int sum = accumulate(all(A), 0);
  int min = (1000000);
  int minid;
  for (int i = 0; i < N; i++) {
    if (abs(A[i])<min) {
      min = abs(A[i]);
      minid = i;
    }
  }
  sum -= A[minid];
  cout << sum << endl;
}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

int dp[501][10][500][2][3];
string str;
string a, b;
int m;

int dfs(int keta, int num, int mod, bool free, int state) {
	if (keta == str.size()) return mod == 0;
	if (dp[keta][num][mod][free][state] != -1) return dp[keta][num][mod][free][state];
	
	int res = 0;
	
	switch (state) {
		case 0: // next up
			FOR(i, num + 1, free ? 10 : str[keta] + 1)
				res += dfs(keta + 1, i, (mod * 10 + i) % m, free | (!free && str[keta] != i), 1);
			break;
			
		case 1: // next down
			REP(i, free ? num : min(num, str[keta] + 1))
				res += dfs(keta + 1, i, (mod * 10 + i) % m, free | (!free && str[keta] != i), 0);
			break;
				
		case 2: // now zero
			if (keta == str.size() - 1) return (free ? 9 : str[keta]) / m;
			else res += dfs(keta + 1, 0, 0, true, 2);
			
			FOR(i, 1, free ? 10 : str[keta] + 1) {
				res += dfs(keta + 1, i, i % m, free | (!free && str[keta] != i), 0);
				res += dfs(keta + 1, i, i % m, free | (!free && str[keta] != i), 1);
			}
			
			break;
	}
	
	return dp[keta][num][mod][free][state] = res % 10000;
}

int solve() {
	fill(dp[0][0][0][0], dp[501][0][0][0], -1);
	REP(i, str.size()) str[i] -= '0';
	int res = dfs(0, 0, 0, false, 2);
	
	return res;
}

int main() {
	cin >> a >> b >> m;
	
	for (int i = a.size() - 1; i >= 0; i--) {
		if (a[i] == '0') a[i] = '9';
		else {
			a[i]--;
			break;
		}
	}
	if (a != "0" && a[0] == '0') a.erase(a.begin());
	
	str = a;
	int na = solve();
	
	str = b;
	int nb = solve();
	
	cout << (nb - na + 10000) % 10000 << endl;
	
	return 0;
}

Measured memory_bytes: 61924
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(), x.end()

int main() {
  ll n;
  cin >> n;
  vector<ll> a;
  for (ll i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      a.push_back(i);
    }
  }
  ll x, y;
  x = a.at(a.size() - 1);
  y = n / x;
  cout << x + y - 2 << endl;
}

Measured memory_bytes: 256
import re
s=input()
flag=False
c=0
d=0
for i in s:
    if(re.search('[A-Z]',i)):d+=1
for i in range(2,len(s)-1):
    if(s[i]=='C'):c+=1
    # print(s[i])
if(s[0]=='A' and c==1 and d==2):print('AC')
else:print('WA')


Measured memory_bytes: 3188
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> t(n), a(n);

    for (int i = 0; i < n; i++) {
        cin >> t[i] >> a[i];
    }

    long long int ts = t[0];
    long long int as = a[0];
    // cout << "ts:as : " << ts << " : " << as << endl;

    long long int ratio;
    for (int i = 1; i < n; i++) {
        if (t[i] >=ts && a[i] >= as) {
            ts = t[i];
            as = a[i];
        } else {
            // ratio = ((double)ts / t[i] > (double)as / a[i]) ? (long long int)ceil((double)ts / t[i]) : (long long int)ceil((double)as / a[i]);
            ratio = max((ts % t[i] == 0) ? ts / t[i] : ts / t[i] + 1,
                        (as % a[i] == 0) ? as / a[i] : as / a[i] + 1);
            ts = t[i] * ratio;
            as = a[i] * ratio;
        }
        // cout << "ts:as : " << ts << " : " << as << endl;
    }

    cout << ts + as << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;

struct State {
	int fives, pay;
};

State comp(const State s1, const State s2) {
	if(s1.fives != s2.fives)
		return s1.fives > s2.fives ? s1 : s2;
	return s1.pay < s2.pay ? s1 : s2;
}


const int INF = 1 << 25;
const int MAX = 100010;
State dp[101][MAX];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	while(cin >> n, n) {

		for(int i = 0; i < n + 1; i++) {
			for(int j = 0; j < MAX; j++) {
				dp[i][j].fives = -1;
				dp[i][j].pay = INF;
			}
		}
		dp[0][0].fives = 0;
		dp[0][0].pay = 0;

		for(int i = 0; i < n; i++) {
			int p, pay;
			cin >> pay;

			for(int j = 0; j < MAX; j++) {
				if(dp[i][j].fives == -1) continue;
				p = pay % 1000;
				// ??????
				dp[i + 1][j] = comp(dp[i + 1][j], dp[i][j]);
				// ?????????
				if(p != 0) {
					if(1000 - p >= 500) {// 500?????????
						int nj = j + 500 - p;
						State ns = State{ dp[i][j].fives + 1, dp[i][j].pay + pay };
						dp[i + 1][nj] = comp(dp[i + 1][nj], ns);
					}
					else {
						int nj = j + 1000 - p;
						State ns = State{ dp[i][j].fives, dp[i][j].pay + pay };
						dp[i + 1][nj] = comp(dp[i + 1][nj], ns);
					}
				}

				// ?????£??????
				if(p <= 500) {
					if(p + 500 <= j) {
						int nj = j - (p + 500);
						State ns = State{ dp[i][j].fives + 1, dp[i][j].pay + pay };
						dp[i + 1][nj] = comp(dp[i + 1][nj], ns);
					}
				}
				else {
					if(p % 500 <= j) {
						int nj = j - p % 500;
						State ns = State{ dp[i][j].fives + 1, dp[i][j].pay + pay };
						dp[i + 1][nj] = comp(dp[i + 1][nj], ns);
					}
				}
			}
		}
		State ans = State{ -1, INF };
		for(int j = 0; j < MAX; j++) {
			if(dp[n][j].fives != -1) {
				ans = comp(ans, dp[n][j]);
			}
		}
		cout << ans.fives << " " << ans.pay << endl;
	}

}

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

int main(){
  long N,K;
  cin >> N >> K;
  
  long H[N];
  
  for(int i=0;i < N; i++){
    cin >> H[i];
  }
  sort(H, H + N, greater<int>());
  
  long sum = 0;
  for (int i= K;i<N;i++){
  sum += H[i];
  }
  cout << sum;
  
  return 0;
}



Measured memory_bytes: 1792
using System;
//using System.Collections;
//using System.Collections.Generic;
using System.Linq;

namespace problem
{
    class Test
    {
        static void Main()
        {
            string[] s = Console.ReadLine().Split(' ');
            int[] x = s.Select(c => int.Parse(c)).ToArray();

            if (x[0] == x[1]) Console.WriteLine("a == b");
            else if (x[0] > x[1]) Console.WriteLine("a > b");
            else Console.WriteLine("a < b");
        }
    }
}


Measured memory_bytes: 9408
s = list(input())
l = len(s)

lst1 = s[0:int((l+1)/2)]
lst2 = s[int((l+1)/2)+1:]
lst2 = s[::-1]

ans =0
for i in range(l//2):
    if lst1[i] != lst2[i]:
        ans += 1

print(ans)    



Measured memory_bytes: 3060
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisect(l,r,f,discrete=True,left=True):
    """
    l,r: l<r int if discrete else float
    f: function defined on [l,...,r] to {False,True}
    if discrete: f defined on Z; else: R
    if left: f satisfies that there uniquely exists d such that iff i<=d then f(i)
    else: iff i>=d then f(i) is True
    return d such as those above
    """
    assert r>l
    if discrete: assert isinstance(l,int) and isinstance(r,int)
    eps=1 if discrete else 10**-12
    if (not left)^f(r): return r if left else r+1
    elif left^f(l): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if (not left)^f(h): l=h
        else: r=h
    return h if not discrete else l if left else r

class RollingHash(object):
    """
    construct: O(N)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=1009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2

    @property
    def len(self):
        return self.__n

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return (hash1,hash2) of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2)

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # initialize
        J={rh.hash(i,i+d):-1 for i in range(n-d+1)}
        for i in range(n-d+1):
            h=rh.hash(i,i+d)
            if J[h]!=-1:
                if i-J[h]>=d: return True
            else: J[h]=i
        return False
    print(bisect(0,n,judge))
resolve()

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

public class Main{
	public static void main(String args[]){
		try{
			new Main();
		}catch(IOException e){
			e.printStackTrace();
		}
	}
	
	public Main() throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line;
		
		while((line = in.readLine()) != null){
			int size = Integer.parseInt(line);
			if(size==0) break;
			Bowl[] game = new Bowl[size];
			for(int i=0; i<size; i++){
				line = in.readLine();
				String[] tmp = line.split(" ");
				int id = Integer.parseInt(tmp[0]);
				int n = tmp.length-1;
				game[i] = new Bowl(id, n);
				for(int m=0; m<n; m++){
					game[i].pins[m] = Integer.parseInt(tmp[m+1]);
				}
				game[i].get_score();
			}
			
			Arrays.sort(game, new score_comp());
			
			for(int i=0; i<game.length; i++){
				System.out.printf("%d %d\n", game[i].id, game[i].score);
			}
		}
		
	}
}

class score_comp implements Comparator<Bowl>{
	public int compare(Bowl b1, Bowl b2){
		int d = 0;
		if((d = b1.score - b2.score) != 0)
			return -d;
		else
			return b1.id - b2.id;
	}
}

class Bowl{
	int[] pins;
	int n;
	int id;
	int score;
	
	public Bowl(int id, int n){
		this.id = id;
		this.n = n;
		this.score = 0;
		pins = new int[n];
	}
	
	public void get_score(){
		int m = 0;
		this.score = 0;
		for(int i=1; i<=10; i++){
			if(i==10){
				for(int k=m; k<n; k++){
					score += pins[k];
				}
			}
			else if(pins[m] == 10){
				score += pins[m] + pins[m+1] + pins[m+2];
				m++;
			}
			else{
				if(pins[m]+pins[m+1] == 10){
					score += pins[m] + pins[m+1] + pins[m+2];
				}
				else{
					score += pins[m] + pins[m+1];
				}
				m+=2;
			}
		}
	}
}

Measured memory_bytes: 12000
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X, i) ((X>>i)&1)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define r_all(a) (a).rbegin(), (a).rend()

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef priority_queue<ll> pq;

const int MOD = 1e9+7;
const int INF = (1<<30);
const ll INFL = (1L<<62);

vvi edges;
vii depth;

void dfs(int x, int d) {
  if (depth[x].ff != -1) return;
  depth[x].ff = d;
  for (auto e : edges[x]) {
    dfs(e, d+1);
  }
}

int main() {
  int n; cin >> n;
  edges.resize(n);
  rep(i,n) {
    depth.pb(mp(-1, i));
  }
  ll sum = 0;
  vi ans(n);
  vi a(n), b(n);
  rep(i,n-1) {
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
    edges[a[i]].pb(b[i]);
    edges[b[i]].pb(a[i]);
  }
  vi c(n);
  rep(i,n) cin >> c[i];
  sort(all(c));
  rep(i,n-1) {
    sum += c[i];
  }
  dfs(0, 0);
  sort(r_all(depth));
  rep(i,n) {
    ans[depth[i].ss] = c[i];
  }

  cout << sum << endl;
  rep(i,n) {
    cout << ans[i] << " \n"[i==n-1];
  }
  return 0;
}


Measured memory_bytes: 1660
a=gets.to_i
 
array=gets.split.map(&:to_i)
 
kei=0
j=0
a.times{
kei+=array[j]
 j=j+1
}
 
 
 
array2=[]
i=0
answer=0
(a-1).times{
      answer=answer+array[i]
      array2<<(2*answer-kei).abs
    
    i=i+1
}


puts array2.min

Measured memory_bytes: 16956
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static const int kModulo = 1000 * 1000 * 1000 + 7;

int main() {
    ios::sync_with_stdio(false);

    string K; cin >> K;
    int D; cin >> D;

    vector< vector< vector<int> > > dp(2, vector<vector<int>>(K.size() + 1, vector<int>(D, 0)));
    dp[1][0][0] = 1;
    for (int i = 0; i < int(K.size()); ++i) {
        int digit = K[i] - '0';
        for (int rest = 0; rest < D; ++rest) {
            for (int add = 0; add < 10; ++add) {
                int next = (rest + add) % D;
                dp[0][i + 1][next] = (dp[0][i + 1][next] + dp[0][i][rest]) % kModulo;
                if (add < digit)
                    dp[0][i + 1][next] = (dp[0][i + 1][next] + dp[1][i][rest]) % kModulo;
                if (add == digit)
                    dp[1][i + 1][next] = (dp[1][i + 1][next] + dp[1][i][rest]) % kModulo;
            }
        }
    }

    int answer = (dp[0][K.size()][0] + dp[1][K.size()][0] - 1) % kModulo;
    if (answer < 0)
        answer += kModulo;
    cout << answer << "\n";
}


Measured memory_bytes: 13184