akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int a, b, c, d[10000];
vector<pair<int, int> >P;
int main() {
	while (true) {
		cin >> a >> b >> c; P.clear();
		if (a == 0)break;
		for (int i = 1; i <= a; i++)cin >> d[i];
		for (int i = b; i <= c; i++) {
			P.push_back(make_pair(d[i] - d[i + 1], i));
		}
		sort(P.begin(), P.end());
		cout << P[P.size() - 1].second << endl;
	}
	return 0;
}

Measured memory_bytes: 1208
N = int(input())
data = [list(map(int,input().split())) for i in range(N)]

A = []

for i in range(N):
    A.append((data[i][1],data[i][0]))

A = sorted(A)

a = 0  #i番目にやった仕事の終了時間
for i in range(N):
    a += A[i][1]
    if a > A[i][0]:
        print('No')
        break
    else:
        continue
else:
    print('Yes')

Measured memory_bytes: 97572
# import bisect
# from collections import Counter, deque
# import copy
from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int,ipti().split()))
    a = list(map(int,ipti().split()))
    a = list(map(lambda x: -1 * x, a))
    heapify(a)

    for _ in range(m):
        mx = -1 * heappop(a)
        mx //= 2
        mx *= -1
        heappush(a, mx)

    print(-sum(a))

if __name__ == '__main__':
    main()

Measured memory_bytes: 69228
a,b,c,d,e,f=map(int,input().split())
noudomax=0
weight=0
weightmax=100*a
sugarmax=0
i=0
while True:
    weight=a*100*i
    if weight>f:
        break
    j=0
    while True:
        if i==j==0:
            j+=1
            continue
        weight=a*100*i+b*100*j
        if weight>f:
            break
        k=0
        while True:
            weight=a*100*i+b*100*j+c*k
            if weight>f:
                break
            l=0
            while True:
                weight=a*100*i+b*100*j+c*k+d*l
                sugar=c*k+d*l
                if weight>f:
                    break
                noudo=100*sugar/weight
                if noudomax<noudo<=100*e/(e+100):
                    #print(noudo,i,j,k,l)
                    weightmax=weight
                    sugarmax=sugar
                    noudomax=noudo
                l+=1
            k+=1
        j+=1
    i+=1

print(weightmax,sugarmax)


Measured memory_bytes: 41052
s = input()
x = 0


for i in range(1,len(s),2):
    if s[i] == 'L' or s[i] == 'U' or s[i] == 'D':
        x += 1

for i in range(0,len(s),2):
    if s[i] == 'R' or s[i] == 'U' or s[i] == 'D':
        x += 1


if x == len(s):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <functional>
const int INF =1e5;
const int MOD = 1e9 + 7;
using namespace std;
typedef pair<int,int> P;
typedef long long lint;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fill(x,y) memset(x,y,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define pb push_back
vector<int> a;
vector<int> b;
int v[10];
bool dfs(int,int,int);

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        rep(i,10) cin>>v[i];
        if(dfs(0,0,0)) cout<<"YES"<<endl;
        else  cout<<"NO"<<endl;
    }
    return 0;
}
bool dfs(int i,int a,int b){
    if(i==10)return true;
    if(a<v[i]) return dfs(i+1,v[i],b);
    if(b<v[i]) return dfs(i+1,a,v[i]);
    if(a>=v[i] && b>=v[i])return false;
    return false;
}



Measured memory_bytes: 3052
n = int(input())
l = [0] * n

import math
m = int(math.sqrt(n)) + 1
for i in range(1, m):
    for j in range(1, m):
        for k in range(1, m):
            a = (i + j + k)**2 - i*j - j*k - k*i
            if a <= n:
                l[a - 1] += 1
for i in l:
    print(i)

Measured memory_bytes: 9248
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
 
dp = [-1 for _ in range(W + 1)] # dp[重量の総和]:= 価値の総和
dp[0] = 0
 
for i in range(N):
  w, v = wv[i]
  for j in range(W, -1, -1):
    if dp[j] >= 0 and j + w <=  W:
      dp[j+w] = max(dp[j+w], dp[j]+v)
      
print(max(dp))

Measured memory_bytes: 45436
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <tuple>
#include <random>
#include <map>
#include <queue>
#include <set>
#include <complex>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>

using namespace std;

typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> P;

const ll INF = 1e15;
const double eps = 1e-6;
typedef tuple<ll, ll, ll> T;

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

int main() {
	ll N, K;
	cin >> N >> K;
	ll m = -1;
	ll big = 0;
	for (int i = 0;i < N;i++) {
		ll a;
		cin >> a;
		if (m == -1)
			m = a;
		else
			m = gcd(m, a);
		big = max(big, a);
	}
	if (big >= K && K % m == 0)
		cout << "POSSIBLE" << endl;
	else
		cout << "IMPOSSIBLE" << endl;
	return 0;
}


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

int main() {
    string S;
    cin>>S;
    ll ans = 0,shiki,now;

    for(int bit=0;bit<(1<<S.size()-1);bit++){
        now=(S[0]-'0');
        shiki=0;
        rep(i,S.size()-1){
            if(bit&(1<<i)){
                shiki+=now;
                now=(S[i+1]-'0');
            }else{
                now=now*10+(S[i+1]-'0');
            }
        }
        shiki+=now;
        ans+=shiki;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

class location {
	int x;
	int y;
	int ti;

	public location(int x, int y, int ti) {
		this.x = x;
		this.y = y;
		this.ti = ti;
	}

	public void print_member_value() {
		System.out.println("ti:" + String.valueOf(this.ti) +",x:" + String.valueOf(this.x) + ", y:" + String.valueOf(this.y) );

	}

}


public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ


		//input
		//	総step数N
		//	時刻tにおける位置(xi,yi)

		Scanner scan = new Scanner(System.in);
		ArrayList<location> points =  new ArrayList<location>();
		int N = scan.nextInt();

		location start_point = new location(0,0,0);
		points.add(start_point);

		for(int i = 0; i < N ; i ++) {
			int ti= scan.nextInt();
			int x = scan.nextInt();
			int y = scan.nextInt();

			location point = new location(x,y,ti);
			//point.print_member_value();
			points.add(point);

		}

		//logic
		//★①
		//		A.xiからxi+1へ行くには最低何step必要か求める
		//		B.yiからyi+1へ行くには最低何step必要か求める
		//		AとBの合計がNを超えたらまずアウト
		//		AとBの合計 = NならOK
		//		AとBの合計 < Nでも、行ったり来たりをしてstep数を稼げば問題ない
		//			ではデータも持ち方をどうするか
		//			→クラスのインスタンス化して、動的配列に順番に格納。インデックスの隣のインスタンス間を比較して、移動が可能かどうか判断
		//				→判断の途中、一つでも移動が不可能な場合があったらbreak

		//②tiの地点から、指定されたstep数で移動できる地点を全部洗いだして、目的の地点と比較して移動できるかどうか判断
		// →計算量が少なくない

		//③


		boolean possible = solve_1(points);


		//output
		//	step Nで、移動可能な範囲であるかどうかの判断結果

		if(possible) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

		//

	}

	public static boolean solve_1(ArrayList<location> points) {

		boolean possible = true;

		for(int j = 0; j < points.size()-1; j ++) {
			//debug pring
			//points.get(j).print_member_value();

			location pre_point = points.get(j);
			location next_point = points.get(j+1);

			int step = next_point.ti - pre_point.ti;
			int x_must_step = next_point.x - pre_point.x;
			int y_must_step = next_point.y - pre_point.y;

			int must_step = x_must_step + y_must_step;
			int surplus_step = step - must_step;

			if(must_step > step) {//1つでも、不可能な旅程が存在した時点で、「No」判定
				possible = false;
				break;
			}else if(must_step == step) {
				continue;
			}else if(must_step < step && (surplus_step % 2 == 0)){//同じ場所に行ったり来たりしてstep数を無駄に稼げばいける(但し、偶数ステップ数でないと、指定時間に元の位置に戻れない)
				continue;
			}else {
				possible = false;
				break;
			}


		}

		return possible;
	}

}


Measured memory_bytes: 93512
//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

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

	if (S.size() <= K) {
		cout << S << endl;
		return 0;
	}

	cout << S.substr(0, K) << "..." << endl;

	return 0;
}

Measured memory_bytes: 3624
S=input()
_S=[]
for s in S:
    if s != "x":
        _S.append(s)
len_S=len(_S)
if  sum([_S[i]!=_S[-i-1] for i in range(len_S//2)]):
    print(-1)
else:
    count=0
    i,m=0,len(S)-1
    while m-i>0:
        if S[i]=="x" and S[m]!="x":
            i+=1
            count+=1
        elif S[i]!="x" and S[m]=="x":
            m-=1
            count+=1
        else:
            i+=1
            m-=1
    print(count)


Measured memory_bytes: 48752
// Template
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <cmath>
#include <complex>
#include <cassert>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, r) for (int i = (l); i < (r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003;
template <typename T> inline bool chmin(T &x, const T &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T &x, const T &y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET{IOSET(){cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

// Main Code
int main() {
    int n;
    string s;
    cin >> n >> s;
    
    vector<int> sum(n + 1, 0);
    rep(i, n) {
        sum[i + 1] = sum[i];
        if (s[i] == 'R') ++sum[i + 1];
    }
    
    int ans = inf;
    rep(i, sum[n], n + 1) {
        chmin(ans, sum[n] - sum[i] + (i - sum[n]));
    }
    
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 4400
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll int64_t
#define all(v) v.begin(), v.end()
#define bitrep(n) for(int bit=0;bit<(1<<n);bit++)

int main() {

ll N,M; cin >> N >> M;

vector<int> ans(N,-1);

vector<int> s(M),c(M);

rep(i,M) cin >> s[i] >> c[i];//input

rep(i,M){
  if(ans[s[i]-1]!=-1&&ans[s[i]-1]!=c[i]){//すでに入力があるマスにべつの数値を要求された場合
    cout << -1 << endl;
    return 0;
  }

  if(s[i]==1&&c[i]==0&&N!=1){//二桁以上で先頭に0を要求された場合
    cout << -1 << endl;
    return 0;
  }
 ans[s[i]-1]=c[i];
}

rep(i,N){//未入力の処理
  if(ans[i]==-1){
    if(i==0&&N!=1) ans[i]=1;
    else ans[i]=0;
  }
}

rep(i,N) cout << ans[i];

cout <<endl;

return 0;
}

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

const double pi = acos(-1);

int main() {
    double a, b, x; cin >> a >> b >> x;
    
    double V = a * b * a / 2;
    double rad;
    if(V > x) rad = atan(2 * x / (a * b * b));
    else rad = atan(a * a * a / (2 * a * a * b - 2 * x));
    
    double ans = 180 * rad / pi;
    printf("%.10f\n", 90 - ans);
}


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

int main() {
    int a, b, ans;
    cin >> a >> b;
    for (int i=a; i<b+1; i++) {
        if (i%10 == i/10000 && i%100/10 == i/1000%10) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
a,b,k=map(int,input().split())

if b-a+1<=2*k:
    for i in range(a,b+1):
        print(i)

else:
    aa=[a+i for i in range(k)]
    bb=[b-j for j in range(k)]
    cc=sorted(aa+bb)
    for c in cc:
        print(c)
    

Measured memory_bytes: 3060
abk = gets.chomp.split
a = abk[0].to_i
b = abk[1].to_i
k = abk[2].to_i

nums = []
k.times do |i|
    num = a + i
    nums << num
    puts num if num <= b
end

k.times do |i|
    num = b - k + i + 1
    puts num if !nums.include?(num) && num <= b && nums.min < num
end

Measured memory_bytes: 1788
#include <stdio.h>
#include <stdint.h>
#include <iostream>
#include <fstream>
#include <cassert>
#include <climits>
#include <vector>
using namespace std;

#define DEBUG (0)

#if DEBUG
#define DPRINTF(...) do { \
    printf("D(L%d) %s: ", __LINE__, __func__); \
    printf(__VA_ARGS__); \
  } while (false)
#else
#define DPRINTF(...)
#endif // DEBUG

struct Node
{
  Node() :
    id_(-1),
    parent_(nullptr),
    left_(nullptr),
    right_(nullptr) { }

  int id_;
  Node* parent_;
  Node* left_;
  Node* right_;
};

void walkInPreorder(Node *node, vector<int> &vec)
{
  if (node == nullptr)
    return;

  vec.push_back(node->id_);
  walkInPreorder(node->left_, vec);
  walkInPreorder(node->right_, vec);
}

void walkInInorder(Node *node, vector<int> &vec)
{
  if (node == nullptr)
    return;

  walkInInorder(node->left_, vec);
  vec.push_back(node->id_);
  walkInInorder(node->right_, vec);
}

void walkInPostorder(Node *node, vector<int> &vec)
{
  if (node == nullptr)
    return;

  walkInPostorder(node->left_, vec);
  walkInPostorder(node->right_, vec);
  vec.push_back(node->id_);
}

int main()
{
  int numOfNodes;
  cin >> numOfNodes; cin.ignore();

  Node *nodes = new Node[numOfNodes];

  for (int i = 0; i < numOfNodes; i++)
  {
    int id, left, right;
    cin >> id >> left >> right;

    nodes[id].id_ = id;

    if (left > -1)
    {
      nodes[id].left_ = &nodes[left];
      nodes[left].parent_ = &nodes[id];
    }

    if (right > -1)
    {
      nodes[id].right_ = &nodes[right];
      nodes[right].parent_ = &nodes[id];
    }
  }

  assert(&nodes[0] != nullptr);
  Node *root = &nodes[0];

  while (root->parent_ != nullptr)
  {
    root = root->parent_;
  }

  {
    vector<int> vec;
    walkInPreorder(root, vec);

    printf("Preorder\n");

    for (uint32_t i = 0; i < vec.size(); i++)
      printf(" %d",  vec[i]);

    printf("\n");
  }

  {
    vector<int> vec;
    vec.clear();
    walkInInorder(root, vec);

    printf("Inorder\n");

    for (uint32_t i = 0; i < vec.size(); i++)
    {
      printf(" %d", vec[i]);
    }

    printf("\n");
  }

  {
    vector<int> vec;
    vec.clear();
    walkInPostorder(root, vec);

    printf("Postorder\n");

    for (uint32_t i = 0; i < vec.size(); i++)
    {
      printf(" %d", vec[i]);
    }

    printf("\n");
  }

  delete[] nodes;

  return 0;
}


Measured memory_bytes: 3240
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++){cin >> A[i];}
  sort(A.begin(), A.end());
  int count=1;
  int ans=0;
  int a=A[0];
  for(int i=1;i<N;i++){
    if(A[i]==a){count++;}
    else{
      if(count%2==1){ans++;}
      a=A[i];
      count=1;
    }
  }
  if(count%2==1){ans++;}
  cout << ans << endl;
}

Measured memory_bytes: 640
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
string A,B,C;
int main(){
    cin>>A>>B>>C;

   int X,Y,Z;
   X=A.size();
   Y=B.size();
   Z=C.size();

   if(A[X-1]==B[0] && B[Y-1]==C[0]){
	   cout<<"YES"<<endl;
   }else{
	   cout<<"NO"<<endl;
   }

    return 0;
}


Measured memory_bytes: 256
<?php
$input = explode(' ', trim(fgets(STDIN)));

$n = (int)$input[0];
$k = (int)$input[1];

$s = trim(fgets(STDIN));
$ary = [];
if ($s[0] === '0') {
	$ary[] = [
		's' => '1',
		'c' => 0,
	];
}
$cnt = 1;
for ($i=1; $i < $n; $i++) { 
	if ($s[$i-1] !== $s[$i]) {
		$ary[] = [
			's' => $s[$i-1],
			'c' => $cnt,
		];
		$cnt = 1;
	}else{
		++$cnt;
	}
	if ($i === $n-1 && $cnt > 0) {
		$ary[] = [
			's' => $s[$i],
			'c' => $cnt,
		];
	}
}
$len = count($ary);
if ($s[$n-1]==='0') {
	$ary[] = [
		's' => '1',
		'c' => 0,
	];
}
// var_dump($ary);

// window
$len = count($ary);
if ($len <= $k*2+1) {
	echo $n;
	exit();
}
$sum = 0;
for ($i=0; $i < $k*2+1; $i++) { 
	$sum += $ary[$i]['c'];
}
$prev = $sum;
$max = $prev;
for ($j=$k*2+1; $j < $len; $j+=2) { 
	$tmp = $prev - $ary[$j-$k*2-1]['c'] - $ary[$j-$k*2]['c'] + $ary[$j]['c'] + $ary[$j+1]['c'];
	$max = max($max, $tmp);
	$prev = $tmp;
}
echo $max;

Measured memory_bytes: 47604
#include<stdio.h>

int main(void){
    int a,b;
    int ans1,ans2;
    scanf("%d %d",&a,&b);
    
    ans1 = a*b;
    ans2 = 2*(a + b);
    
    printf("%d %d\n",ans1,ans2);
    
    return 0;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
#define ll long long
#define Whitebeard ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
int main()
{
    Whitebeard;
    int a,b,c=0,d,e=2;
    vector<int>v1;
    vector<int>v2;
    vector<int>v;
    cin>>a;
    for(int i=1; i<=a; i++)
    {
        v.push_back(i);
    }
    for(int i=0; i<a; i++)
    {
        cin>>b;
        v1.push_back(b);

    }
    for(int i=0; i<a; i++)
    {
        cin>>b;
        v2.push_back(b);

    }
    if(v1==v2){cout<<0;return 0;}
    bool f=false;
    do
    {
        if(f==true)
        {
            c++;
            if(v==v1 || v==v2)
            {
                cout<<c-1;
                return 0;
            }
        }
        if(v==v1 || v==v2)
        {
            c++;
            f=true;
        }

    }
    while(next_permutation(v.begin(),v.end()));

}


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

using namespace std;

int main()
{
    int i,n,k;
    int s=0;
    vector<int> a;
    cin>>n>>k;
    a.resize(n+1);
    for(i=1;i<=n;i++) cin>>a[i];
    sort(a.begin(),a.end());
    i=0;
    while(i!=k){
    s+=a[n-i];
    i++;
    }
    cout<<s;


}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
from itertools import chain

@lru_cache(None) # 再帰にしつつ、下から計算することで再帰処理をしない
def subsets(U): # O(2^k)
    # base case
    if U == 0:
        return (0,)
    # recursion
    d = U.bit_length() - 1
    U ^= 1 << d
    prev = subsets(U)
    return tuple(chain(prev, (U | 1 << d for U in prev)))

def resolve():
    n = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(n))

    # O(n^2 * 2^n)
    state_to_score = [0] * (1 << n)
    for U in range(1 << n):
        for i in range(n):
            if (U >> i) & 1 == 0:
                continue
            for j in range(i):
                if (U >> j) & 1:
                    state_to_score[U] += A[i][j]

    # dp[i][U] : i まで見て U <= {1, ..., n} を grouping したときの max
    # msb(U) = i ならば dp[i][U] = dp[i + 1][U] = ... = dp[n - 1][U] なので dp は使いまわせる
    # dp[i + 1][U | 1 << (i + 1)] = max((V + {i + 1} の score) + dp[i][W]) for all V + W = U
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for i in range(n): # 既に U = 0, ..., 2^i - 1 までは確定している
        for U in range(1 << i): # O(2^i) これから 2^i, ..., 2^(i + 1) - 1 を確定させる
            for V in subsets(U): # O(2^k) where k = popcount(U)
                W = U ^ V
                dp[U | 1 << i] = max(dp[U | 1 << i], state_to_score[V | 1 << i] + dp[W])

    # 計算量は sum_{0 <= i < n} sum_{0 <= U < 2^i} 2 ^ popcount(U)
    # = sum_{0 <= i < n} sum_{0 <= k <= i} iCk * 2^k = (3^n - 1) / 2
    print(dp[-1])
resolve()

Measured memory_bytes: 258056
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdlib>
using namespace std;
int a,b;
int main(){
	scanf("%d%d",&a,&b);
	if((a+b)%2==0) printf("%d\n",(a+b)/2);
		else printf("%d\n",(a+b)/2+1); 
}


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

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

graph = [[] for _ in range(n)]
for a, b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

q = queue.Queue()
q.put(0)
point = [0] * n
seen = [0] * n
seen[0] = 1

while not q.empty():
    i = q.get()
    for j in graph[i]:
        if seen[j] == 0:
            point[j] = i + 1
            seen[j] = 1
            q.put(j)

print('Yes')
for x in range(1, n):
    print(point[x])

Measured memory_bytes: 74024
n = int(input())
l = sorted([input() for _ in range(n)])
x = l[0]
count = 0
score = 0
for s in l[1:]:
    if x==s:
        count+=1
    else:
        score+=count%2==0
        count=0
    x = s
score+=count%2==0
print(score)

Measured memory_bytes: 58072
#include <stdio.h>
#include <stdlib.h>

int main()
{
   int s,z,c,a,b,x,i,j,count=0;
   scanf("%d%d%d%d",&a,&b,&c,&x);
   for(i=0;i<=a;i++)
   {
       for(j=0;j<=b;j++)
       {
           for(z=0;z<=c;z++)
           {
               s=i*500+j*100+z*50;
               if(s==x)
                count++;
           }
       }
   }

   printf("%d",count);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
#define mp make_pair
signed main(){
    int n; cin>>n;
    vi v(n);
    rep(i,n)cin>>v[i];
    int m;
    cin>>m;
    int ans=0;
    rep(i,m){
        int t;
        cin>>t;
        int imax=n;
        int imin=0;
        int mid;
        while(imax>imin){
            mid=(imax+imin)/2;
            if(v[mid]>t)imax=mid;
            else if(v[mid]<t)imin=mid+1;
            else {
                ans++;
                break;
            }
        }
    }
    cout<<ans<<endl;
}

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

int main() {
  int n;
  cin >> n;
  int ans = 0;
  for (int i = 0; i < n; i++){
    int l, r;
    cin >> l >> r;
    ans += r - l + 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>

int main(void){
    long long n,k,ans=0;
    scanf("%lld%lld",&n,&k);
    if (k==0){
        ans=n*n;
    } else {
        for (int i=k+1; i<=n; i++){
            ans+=(n/i)*(i-k)+fmax((n%i)-k+1,0);
        }
    }
    printf("%lld\n",ans);
	return 0 ;
}

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

int main(void)
{
    int number1, number2, number3;

    cin >> number1 >> number2 >> number3;

    if (number1 < number2 && number2 < number3) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 1156
#include <iostream>
#include <vector>
#include <utility>

int N;
std::vector<std::vector<std::pair<int, int>>>  graph;
std::vector<int> a_way_of_painting ;

void Search(int target_node, int parent, int color) {
  a_way_of_painting[target_node] = color;
  for (auto e: graph[target_node]) {
    if(e.first == parent) {
      continue;
    } else if (e.second & 1) {
      Search(e.first, target_node, 1-color);
    } else {
      Search(e.first, target_node, color);
    }
  }
}

int main() {
  std::cin >> N;
  graph.assign(N, std::vector<std::pair<int, int>>());
  a_way_of_painting.assign(N, 0);
  for (int i = 0; i < N-1; ++i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    --u;
    --v;
    graph[u].push_back(std::make_pair(v, w));
    graph[v].push_back(std::make_pair(u, w));
  }
  Search(0, -1, 1);
  for (auto color: a_way_of_painting) {
    std::cout << color << std::endl;
  }
}


Measured memory_bytes: 8960
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from sys import stdin
from math import isinf


def generate_adj_table(v_table, _init_adj_table):
    for each in v_table:
        start, end, weight = map(int, each)
        _init_adj_table[start][end] = weight

    return _init_adj_table


def floyd(_adj_table):
    for k in _range:
        for i in _range:
            for j in _range:
                _adj_table[i][j] = min(_adj_table[i][j],
                                       _adj_table[i][k] + _adj_table[k][j])
    return _adj_table


def solve(_adj_table):
    after_floyd_table = floyd(_adj_table)

    negative = False
    for m in _range:
        if after_floyd_table[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
        return None
    else:
        for each in after_floyd_table:
            print(' '.join(('INF' if isinf(ele) else str(ele) for ele in each)))

    return after_floyd_table


if __name__ == '__main__':
    _input = stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    info_list = map(lambda x: x.split(), _input[1:])
    _range = range(vertices)

    init_adj_table = tuple([float('inf')] * vertices for i in range(vertices))
    for n in _range:
        init_adj_table[n][n] = 0

    adj_table = generate_adj_table(info_list, init_adj_table)
    solve(adj_table)

Measured memory_bytes: 8860
#include<bits/stdc++.h>
using namespace std;
                    
                    
int main(){
    string s, ans;
    int n;
    cin >> s;
    n = s.size();
    ans = "Yes";

    if(s.substr(0, (n - 1) / 2) != s.substr((n + 3) / 2 - 1, n)){
        ans = "No";
    }

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

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

int gcd(int a, int b){
    if(a < b){
        int tmp = a;
        a = b;
        b = tmp;
    }
    int r = a % b;
    if(r == 0) return b;
    a = b;
    b = r;
    return gcd(a, b);
}

int main(){
    int x, y;
    while(cin >> x >> y){
        cout << gcd(x, y) << endl;
    }
}



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

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

    bool iscat = true;
    for(int i=0; i<(int)str.length()-1; i++){
        if((str[i]=='m' && str[i+1]=='w')
           || (str[i]=='e' && str[i+1]=='e')
           || (str[i]=='w' && str[i+1]=='m')){
            iscat=false;
            break;
        }
    }

    int cm=0, ce=0, cw=0;
    for(int i=0; i<(int)str.length(); i++){
        if(str[i]=='m') cm++;
        if(str[i]=='e') ce++;
        if(str[i]=='w') cw++;
        if(cm<ce || cm<cw || ce<cw){
            iscat=false;
            break;
        }
    }
    if(cm!=ce || cm!=cw){
        iscat=false;
    }
    
    if(iscat){
        cout << "Cat" << endl;
    }else{
        cout << "Rabbit" << endl;
    }
    return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
int main(){
    int i,n;cin>>n;
    string m;
    char p;
    bool is=true;
    map<string,int> w;
    for(i=0;i<n;i++){
        cin>>m;
        if(i!=0){
            if(w[m]!=0){
                is=false;
            }
            if(p!=m[0]){
                is=false;
            }
        }
        w[m]=1;
        p=m[m.size()-1];
    }
    cout<<(is?"Yes":"No")<<endl;
}

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

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

    int win = 0, lose = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == 'o')
        {
            win++;
        }
        else
        {
            lose++;
        }
        
        
    }
    if (15 - s.size() + win >= 8)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    
    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <utility>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const double EPS = 1e-10;

vector<int> x;
int n, s;
vector<vector<ll>> dp(201, vector<ll>(100001, 0)); // x_{i-1} まで見た後に ss になる順列の数

ll fact(ll m) {
    ll ret = 1;
    for(ll i=1;i<=m;++i) {
        ret *= i;
        ret %= MOD;
    }
    return ret;
}

ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s;
    x.resize(n);
    for(int i=0;i<n;++i){
        cin >> x[i];
    }
    sort(x.rbegin(), x.rend());

    dp[0][s] = fact(n);
    for(int i=0;i<n;++i) {
        ll p = modpow(n-i, MOD-2);
        for(int ss=0;ss<=s;++ss) {
            dp[i+1][ss%x[i]] += (dp[i][ss]*p) % MOD;
            dp[i+1][ss%x[i]] %= MOD;
            dp[i+1][ss] += (((dp[i][ss]*p) % MOD)*(n-i-1)) % MOD;
            dp[i+1][ss] %= MOD;
            // if(dp[i][ss]) cerr << "dp[" << i << "][" << ss << "] = " << dp[i][ss] << endl;
        }
    }

    ll ans = 0;
    for(int ss=0;ss<=s;++ss) {
        // if(dp[n][ss]) cerr << "dp[" << n << "][" << ss << "] = " << dp[n][ss] << endl;
        ans += (ss*dp[n][ss])%MOD;
        ans %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 158592
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	deque<char> dq;
	int ret=0;
	string s; cin>>s;
	for (char ch : s)
		dq.push_back(ch);
	while(!dq.empty()) {
		if(dq.size()==1) break;
		if(dq.front()==dq.back()) dq.pop_front(), dq.pop_back();
		else {
			if(dq.front()=='x') dq.pop_front(), ret++;
			else if(dq.back()=='x') dq.pop_back(), ret++;
			else {
				cout<<-1<<"\n";
				return 0;
			}
		}
	}
	cout<<ret<<"\n";
	return 0;
}

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

int main(){
    vector<int> a;
    int b;
    while(cin >> b)
        a.push_back(b);
    sort(a.rbegin(),a.rend());
    for(int i = 0; i<3; i++)
        cout << a[i] << endl;
    return 0;
}



Measured memory_bytes: 3104
is_prime = [True]*100001
is_prime[0] = False
is_prime[1] = False
for i in range(2,int(100000**0.5)+1):
  if not is_prime[i]:
      continue
  for j in range(i*2,100001,i):
      is_prime[j] = False
S = [0]*100001
for N in range(3,100001,2):
  if is_prime[N] and is_prime[(N+1)//2]:
    S[N] += 1
for N in range(3,100001):
    S[N] += S[N-1]
Q = int(input())
for k in range(Q):
  l,r = map(int,input().split())
  print(S[r]-S[l-1])

Measured memory_bytes: 7284
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>

using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	ll S;
	cin >> S;
	cout << 1110 - S << "\n";
	return 0;
}

Measured memory_bytes: 256
H,W=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(H)]
for i in range(H):
   for j in range(W):
      l[i][j]%=2
sw=0
ans=[]
for i in range(H):
   if i%2==0:
      for j in range(W):
         if sw==1:
            ans.append((i+1,j+1))
         if l[i][j]==1:
            sw=1 if sw==0 else 0
            if sw==1:
               ans.append((i+1,j+1))
            if sw==0:
               ans.append(0)
   else:
      for j in reversed(range(W)):
         if sw==1:
            ans.append((i+1,j+1))
         if l[i][j]==1:
            sw=1 if sw==0 else 0
            if sw==1:
               ans.append((i+1,j+1))
            if sw==0:
               ans.append(0)
f_ans=[]
for i in range(len(ans)-1):
   if ans[i]!=0 and ans[i+1]!=0:
      f_ans.append((*ans[i],*ans[i+1]))
print(len(f_ans))
for i in f_ans:print(*i)

Measured memory_bytes: 48936
#define ll long long int
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
int main()
 {
//code
         ll n,m,i,j,k;
         cin>>n>>m;
         char a[n][m];
         ll dp[n+1][m+1];
		for(i=0;i<n;i++)
         {
         	for(j=0;j<m;j++)
         	{
			 cin>>a[i][j];
			 dp[i][j]=0;
			 
		    }
		 }
		 dp[0][0]=1;
		 for(j=1;j<n;j++)
		 {
		 	if(a[0][j]=='.')
		 	dp[0][j]=dp[0][j-1];
		 	else
		 	dp[0][j]=0;
		 }
		 for(i=1;i<n;i++)
		 {
		 	if(a[i][0]=='.')
		 	dp[i][0]=dp[i-1][0];
		 	else
		 	dp[i][0]=0;
		 }
		for(i=1;i<n;i++)
         {
         	for(j=1;j<m;j++)
         	{
         					{
					if(a[i][j]=='.')
					dp[i][j]=dp[i-1][j]+dp[i][j-1];
					else
					dp[i][j]=0;	
					dp[i][j]%=mod;
				}
           }
        }
       cout<<dp[n-1][m-1]%mod;
}

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

int main(){
	char c;
	while(1){
		scanf("%c",&c);
		if(c>='a'&&c<='z'){
			c-='a'-'A';
			cout << c;
		}
		else if(c>='A'&&c<='Z'){
			c+='a'-'A';
			cout << c;
		}
		else if(c=='\n'){
			break;
		}
		else{cout << c;}
	}
	cout << endl;

}

Measured memory_bytes: 1144
#include <bits/stdc++.h>
#define rep(i,a,b) for(auto i=(a);i<(b);i++)
#define per(i,a,b) for(auto i=(a);i>=(b);i--)
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define int_inf 0x3f3f3f3f
#define int_max 2147483647
#define ll_max 9223372036854775807
#define ull_max 18446744073709551615
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lowbit(x) (x)&(-x)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define eps 1e-8
#define all(v) (v.begin(),v.end())
#define db double
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const double pi=acos(-1.0);
const double inf = 1e100;
template<class T>
inline T read()
{
	T x=0,f=1;char s=getchar();
	while(s<'0'||s>'9') {if(s=='-')f=-1;s=getchar();};
	while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-48;s=getchar();};
	return x*f;
}
template<typename T>
inline void wri(T x)
{
	if(x<0){x=-x;putchar('-');};
	if(x/10) wri(x/10);
	putchar(x%10+48);
}
template<typename T>
inline void print(T x,char s)
{
	wri(x);
	putchar(s);
}
template<typename T>
T gcd(T a,T b)
{
	return b==0?a:gcd(b,a%b);
}
//关闭流同步就不能手写读入优化啦
map<string,int>p;
int t;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
    	string s;
    	cin>>s;
    	p[s]++;
	}
	cout<<"AC x "<<p["AC"]<<endl;
	cout<<"WA x "<<p["WA"]<<endl;
	cout<<"TLE x "<<p["TLE"]<<endl;
	cout<<"RE x "<<p["RE"]<<endl;
    return 0;
}



Measured memory_bytes: 3684
#include<iostream>

using namespace std;

int main() {
	int b,r,g,c,s,t;
	int coin,bonus;
	bool star;
	
	
	while (cin >> b, cin >> r, cin >> g, cin >> c, cin >> s, cin >> t, b+r+g+c+s+t ) {
		coin = 100;
		bonus = 0;
		star = false;
		
		for ( int i = 0; i < t; i++ ) {
			if ( star == true ) {
				star = false;
			} else if ( bonus > 0 ) {
				coin = coin - 2;
			} else {
				coin = coin - 3;
			}
			if ( bonus > 0 ) {
				coin = coin + 15;
				bonus --;
			} else if ( s > 0 ) {
				star = true;
				s--;
			} else if ( c > 0 ) {
				coin = coin + 2;
				c--;
			} else if ( g > 0 ) {
				coin = coin + 7;
				g--;
			} else if ( r > 0 ) {
				bonus = 3;
				coin = coin + 15;
				r--;
			} else if ( b > 0 ) {
				bonus = 5;
				coin = coin + 15;
				b--;
			}
				
		}
		cout << coin << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1160
import java.io.IOException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			n = scanner.nextInt();
			k = scanner.nextInt();
			if ((n | k) == 0)
				break;
			num = new int[n];
			for (int i = 0; i < n; i++)
				num[i] = scanner.nextInt();
			set = new HashSet<String>();
			b = new boolean[n];
			dfs(0, "");
			System.out.println(set.size());
		}
	}

	private void dfs(int x, String s) {
		if (x == k) {
			set.add(s);
			return;
		}
		for (int i = 0; i < n; i++) {
			if(b[i])
				continue;
			b[i] = true;
			dfs(x + 1, s + num[i]);
			b[i] = false;
		}
	}

	int n, k;
	int[] num;
	boolean[] b;
	Set<String> set;
}

Measured memory_bytes: 26532
#define _CRT_SECURE_NO_WARNINGS
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator<<(ostream & os, vector<T> const &);
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream & os, tuple<T...> const & t){ _ot<0>(os, t); return os; }
template<class T, class U> ostream & operator<<(ostream & os, pair<T,U> const & p){ return os << "(" << p.first << ", " << p.second << ") "; }
template<class T> ostream & operator<<(ostream & os, vector<T> const & v){ rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os; }
#ifdef DEBUG
#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<mt(__VA_ARGS__)<<" ["<<__LINE__<<"]"<<endl)
#else
#define dump(...)
#endif
ll const mod = 1000000007;
int const inf = 1LL<<29;

typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src_, int dst_, Weight weight_) :
        src(src_), dst(dst_), weight(weight_) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

int n,m,c;
Graph g;
int dp[110][110];

int solve(){
    int ans = inf;
    // 距離、今いる頂点、0にした回数
    // 距離がcより小さくなったら
    typedef tuple<int,int,int> state;
    priority_queue<state> q;
    rep(i,101)rep(j,101) dp[i][j] = inf;
    q.emplace(0,0,0);
    dp[0][0] = 0;
    while(q.size()){
        int d,v,r;
        tie(d,v,r) = q.top();
        q.pop();
        d*=-1;
        if(dp[v][r] < d) continue;
        if(r > n) continue;
        if(d > c) continue;
        if(v==n-1) ans = min(ans,r);
        for(auto & e : g[v]){
            if(dp[e.dst][r] > d+e.weight){
                dp[e.dst][r] = d+e.weight;
                q.emplace(-(d+e.weight), e.dst, r);
            }
            if(dp[e.dst][r+1] > d){
                dp[e.dst][r+1] = d;
                q.emplace(-d, e.dst, r+1);
            }
        }
    }
    return ans;
}

int main(){
#ifdef LOCAL
    cout << "TEST" << endl;
    freopen("in","r",stdin);
#endif // LOCAL

    while(cin >> n >> m >> c && n){
        g.assign(n,{});
        rep(i,m){
            int f,t,c;
            cin >> f >> t >> c;
            f--, t--;
            g[f].eb(f,t,c);
        }
        cout << solve() << endl;
    }
}

Measured memory_bytes: 1500
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    int i, n;
    long c = 0;
    cin >> n;
    vector<int> h(n), dp(n);
    for (i = 0; i < n; ++i)
        cin >> h[i];
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    dp[2] = min(abs(h[2] - h[0]), dp[1] + abs(h[2] - h[1]));
    for (i = 3; i < n; ++i)
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
    cout << dp[n - 1];
    return 0;
}

Measured memory_bytes: 1024
from math import sqrt, pow

def get_distance(xi, yi, xj, yj):
  return sqrt(pow(xi - xj, 2) + pow(yi - yj, 2))

def solve():
  n = int(input())
  locations = [list(map(int, input().split())) for _ in range(n)]
  
  distance = 0
  
  for i, [xi, yi] in enumerate(locations):
    if i+1 == len(locations):
      remain = locations[:i]
    else:
      remain = locations[:i] + locations[i+1:]
    
    for xj, yj in remain:
      distance += get_distance(xi, yi, xj, yj)
  
  return distance / n

print(solve())

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;
#define rep(i,s,e) for(ll i = (ll)(s); i < (ll)(e); ++i)
#define per(i,s,e) for(ll i = (ll)(s)-1; i >= (ll)(e); --i)

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;

template<class T>
bool ChangeMax(T&a,const T&b){
  if(a >= b) return false;
  a = b;    return true;
}

template<class T>
bool ChangeMin(T&a,const T&b){
  if(a <= b) return false;
  a = b;    return true;  
}

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int n,x; cin >> n >> x;
  vector<int> a(n); cin >> a;
  vector<int> v(n,1001001001);
  ll ans = 2010 * (1e+9);
  rep(i,0,n){
    ll now = i*x;   
    rep(j,0,n){
      ChangeMin(v[j], a[(j-i+n)%n]);
      now += v[j];
    }
    ChangeMin(ans, now);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
x = 1
for i in range(n):
    if a[i]==x:
        x += 1
if x==1:
    print(-1)
else:
    print(n-x+1)


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

int main()
{
  string s,p;
  cin>>s>>p;
  s+=s;
  for (int i = 0; i < s.size()-p.size()+1; ++i)
  {
    bool flag=true;
    for (int j = 0; j < p.size(); ++j)
    {
      if(s[i+j]!=p[j])
      {
        flag=false;
        break;
      }
    }
    if(flag)
    {
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
}


Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
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() {
  ll a,b,x;
  cin>>a>>b>>x;
  //////////
  bool aok,bok;
  ll ans=0;
  aok=a%x==0;
  bok= b%x==0;
 if(aok){
    ans=b/x-a/x+1;   
 }
  else{
    ans=b/x-a/x;
    
  }

  
  
  cout<<ans<<endl;
}









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

using namespace std;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                        \
	sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
	{
sim > struct rge
{
	c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug
{
#ifdef LOCAL
	~debug()
	{
		cerr << endl;
	}
	eni(!=) cerr << boolalpha << i;
	ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d)
{
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
	sim dor(const c &)
	{
		ris;
	}
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define forn(i, n) for (ll i = 0; i < int(n); i++)
#define rfor(n, i) for (ll i = (n - 1); i >= 0; --i)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
#define len(V) (int)V.size()
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define M_PI 3.14159265358979323846
#define EPS 1e-7

void solve()
{
	int n, m; cin >> n >> m;
	vector<int> g[n + 1];
	forn(i, m)
	{
		int x, y; cin >> x >> y;
		x--, y--;
		g[x].pb(y);
		g[y].pb(x);
	}
	for (int i = 0; i < n; ++i) cout << g[i].size() << endl;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
}

Measured memory_bytes: 3604
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
long long n,k;
long long ans;
int main()
{
    scanf("%lld%lld",&n,&k);
    ans=k;
    for(int i=2;i<=n;i++)
        ans*=(k-1);
    printf("%lld",ans);//
}


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

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

pub fn gcd(a: u32, b: u32) -> u32 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

pub fn divisor(n: u32) -> Vec<u32> {
    let mut res = Vec::new();
    for i in (1..).take_while(|x| x * x <= n) {
        if n % i == 0 {
            res.push(i);
            if i != n / i {
                res.push(n / i);
            }
        }
    }
    res.sort();
    res
}

fn main() {
    input! {
        a: u32,
        b: u32,
        k: usize,
    }
    let mut v = Vec::new();
    for i in 1..101 {
        if a % i == 0 && b % i == 0 {
            v.push(i);
        }
    }
    println!("{}", v[v.len()-k]);
}


Measured memory_bytes: 4352
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define ull unsigned long long
#define EPS 1e-8
using namespace std;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
const double pi = acos(-1.0);
int read()
{
	int ret=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret;
}
string s;
int main()
{
 	#ifdef TEST
	 	freopen("input.txt","r",stdin);
	#endif
	cin>>s;
	for(int i=0;i<s.length()-8;i++)
	{
		cout<<s[i];
	}
	return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;


int n,m,k;

int main(){
	cin >> n >> m >> k;
	
	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++){
			if(i*n+j*m-2*i*j==k){
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	
	cout << "No" << endl;
	
}

Measured memory_bytes: 256