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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

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

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF = 1e9;
const ll INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

ll H, W;

ll cost(ll a, ll b, ll c)
{
    return max({a, b, c}) - min({a, b, c});
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

ll func(ll cx, ll cy)
{
    ll ans = cost((H - cy) * W, cx * cy, (W - cx) * cy);
    ans = min(ans, cost(cx * H, cy * (W - cx), (H - cy) * (W - cx)));
    ans = min(ans, cost(cy * W, cx * (H - cy), (W - cx) * (H - cy)));
    ans = min(ans, cost((W - cx) * H, cx * cy, (H - cy) * cx));
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> H >> W;

    ll ans = INFLL;

    {
        ll cx = W / 2;
        REP(cy, 1, H) {
            ans = min(ans, func(cx, cy));
        }
    }

    {
        ll cy = H / 2;
        REP(cx, 1, W) {
            ans = min(ans, func(cx, cy));
        }
    }

    if (W >= 3) {
        ll tmp_w = ceil(W, 3);
        ans = min(ans, cost(tmp_w * H, tmp_w * H, (W - tmp_w * 2) * H));
        tmp_w = W / 3;
        ans = min(ans, cost(tmp_w * H, tmp_w * H, (W - tmp_w * 2) * H));
    }

    if (H >= 3) {
        ll tmp_h = ceil(H, 3);
        ans = min(ans, cost(tmp_h * W, tmp_h * W, (H - tmp_h * 2) * W));
        tmp_h = H / 3;
        ans = min(ans, cost(tmp_h * W, tmp_h * W, (H - tmp_h * 2) * W));
    }

    assert(ans >= 0);
    cout << ans << endl;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{
  char s[11],t[11],u[11];
  int a,b;
  scanf("%s%s",s,t);
  scanf("%d%d",&a,&b);
  scanf("%s",u);
  if(strcmp(s,u)==0)
    a-=1;
  else
    b-=1;
  printf("%d %d",a,b);
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 200000

typedef struct{
    int parent;
    int left;
    int right;
}gNode;

int r_search();
void Inorder(int);
void Preorder(int);
void Postorder(int);

int n;
gNode Node[MAX];

int main(){
    int i;
    int id, left, right, root;

    scanf("%d", &n);
    for(i = 0 ; i < n ; i++){
        Node[i].parent = -1;
        Node[i].left = -1;
        Node[i].right = -1;
    }

    for(i = 0 ; i < n ; i++){
        scanf("%d%d%d", &id, &left, &right);
        Node[id].left = left;
        Node[id].right = right;

        //親の設定
        if(left != -1)Node[left].parent = id;
        if(right != -1) Node[right].parent = id;
    }

    //rootを調べんで〜
    root = r_search();

    printf("Preorder\n");
    Preorder(root);
    printf("\n");
    printf("Inorder\n");
    Inorder(root);
    printf("\n");
    printf("Postorder\n");
    Postorder(root);
    printf("\n");

    return 0;
}

int r_search(){
    for(int i = 0 ; i < n ; i++){
        if(Node[i].parent == -1) return i;
    }
    return 0;
}

void Inorder(int id){
    if(id == -1) return;
    Inorder(Node[id].left);
    printf(" %d", id);
    Inorder(Node[id].right);
}

void Preorder(int id){
    if(id == -1) return;
    printf(" %d", id);
    Preorder(Node[id].left);
    Preorder(Node[id].right);
}

void Postorder(int id){
    if(id == -1) return;
    Postorder(Node[id].left);
    Postorder(Node[id].right);
    printf(" %d", id);
}



Measured memory_bytes: 2080
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RNG(i,from,to) for(int i=(from); i<(int)(to); i++)
#define gcd(i,j) __gcd((i), (j))
typedef long long ll;
typedef pair<int, int> pii;
template<typename T> void show(T e){ cout << e << endl; }
template<typename T> void show(const vector<T>& v){ for(const auto& e : v){ cout << e << " "; } cout << endl; }
template<typename T> void show(const vector<vector<T>>& vv){ for(const auto& v : vv){ show(v); } }
template<class Iter> void show(Iter first, Iter last){ for(auto it=first; it != last; it++){ cout << *it << " "; }; cout << endl; }
const ll DVSR = 10e9+7;

int main(int argc, char const *argv[])
{
  ll N; cin >> N;
  cout << (N/2 + N%2) * (N/2) << endl;
  return 0;
}


Measured memory_bytes: 256
import sys

sx, sy, tx, ty = map(int, sys.stdin.readline().rstrip().split())

path = ""
path_s = ""
for _ in range(tx - sx):
    path_s += "R"
for _ in range(ty - sy):
    path_s += "U"
path_e = ""
for _ in range(tx - sx):
    path_e += "L"
for _ in range(ty - sy):
    path_e += "D"

path = path_s + path_e + "DR" + path_s + "UL" + "UL" + path_e + "DR"
print(path)

Measured memory_bytes: 40172
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yay!")
    else:print(":(")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
n = ip()                                     #入力整数1つ
#a,b= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#c = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
s = 1
for i in range(1,n):
    if max(a[:(i+1)]) == a[i]: s+=1
print(s)

Measured memory_bytes: 13844
def calc():
    n, m = map(int, input().split())
    x = -1
    y = -1
    z = -1
    for i in range(0, m):
        s, c = map(int, input().split())
        if s == 1:
            if (n == 3 or n == 2) and c == 0:
                return -1
            if x == -1:
                x = c
            elif x != c:
                return -1
        elif s == 2:
            if y == -1:
                y = c
            elif y != c:
                return -1
        else:
            if z == -1:
                z = c
            elif z != c:
                return -1
    if n == 1:
        x = max(x, 0)
        res = x
    elif n == 2:
        x = max(x, 1)
        y = max(y, 0)
        res = x * 10 + y
    else:
        x = max(x, 1)
        y = max(y, 0)
        z = max(z, 0)
        res = x * 100 + y * 10 + z
    if n != len(str(res)):
        return -1
    return res


print(calc())


Measured memory_bytes: 3064
#!/usr/bin/env python3
def main():
    def expected_val(limit):
        return (1 + limit) / 2

    N, K = map(int, input().split())
    P = [int(x) for x in input().split()]

    lst = [0]
    res = 0
    for p in P:
        # res += (p + 1) / 2
        res += expected_val(p)
        lst.append(res)
    ans = 0
    for i in range(N - K + 1):
        res = lst[i + K] - lst[i]
        ans = res if res > ans else ans
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 100488
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb(in,tmp) in.push_back(tmp)
#define all(in) in.begin(),n.end()
#define PI acos(-1)
using namespace std;
int main(){
  int a,b;
  while(cin>>a>>b)cout<<a+b<<endl;
}

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

// clang-format off
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template <typename T> T clamp(T val, T min, T max) { return val < min ? min : (max < val ? max : val); }
template <typename T> size_t max_index(T begin, T end) { return distance(begin, max_element(begin, end)); }
template <typename T> size_t min_index(T begin, T end) { return distance(begin, min_element(begin, end)); }
// clang-format on

#define int long long
#define YES "Yes"
#define NO  "No"

using namespace std;

signed main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  bool flag = true;
  int num = 0;

  int x; cin >> x;
  int a; cin >> a;
  int b; cin >> b;

  x -= a;
  // x -= (x / b) * b;
  x %= b;

  cout << x << endl;


  // cout << num << endl;
  // cout << (flag ? YES : NO) << endl;
  
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const (
	SENTINEL = 1000000000
)

type Alds15b struct {
	scanner      *bufio.Scanner
	f            func(a ...interface{}) (n int, err error)
	S            []int
	compareCount int
	n            int
	L            []int
	R            []int
}

func main() {
	a := NewAlds15b()
	a.main()
}

func NewAlds15b() *Alds15b {
	a := &Alds15b{}
	return a
}

func (a *Alds15b) main() {
	scanner := bufio.NewScanner(os.Stdin)
	a.handle(scanner, fmt.Print)
}

func (a *Alds15b) handle(scanner *bufio.Scanner, f func(a ...interface{}) (n int, err error)) {

	a.scanner = scanner
	a.f = f
	a.compareCount = 0

	scanner.Split(bufio.ScanWords)

	scanner.Scan()
	a.n, _ = strconv.Atoi(scanner.Text())
	a.S = make([]int, a.n)
	for i := 0; i < a.n; i++ {
		scanner.Scan()
		a.S[i], _ = strconv.Atoi(scanner.Text())
	}
	// +1で配列の半分の数を確保、更に+1でSENTINEL分を確保
	a.L = make([]int, (a.n/2)+1+1)
	a.R = make([]int, (a.n/2)+1+1)

	a.mergeSort(0, a.n)

	res := strings.TrimRight(fmt.Sprintf("%+v", a.S)[1:], "]") + "\n"
	res += strconv.Itoa(a.compareCount) + "\n"
	f(res)
}

// mid, rightはend
func (a *Alds15b) mergeSort(left, right int) {
	//0 1
	if left+1 >= right {
		return
	}
	mid := (left + right) / 2

	//fmt.Printf("left:%d, mid:%d, right:%d\n", left, mid, right)

	a.mergeSort(left, mid)
	a.mergeSort(mid, right)
	a.merge(left, mid, right)
}

func (a *Alds15b) merge(left, mid, right int) {
	// これだと要素数がスライスと同じになってしまうためSENTINELを置けない
	//a.L = a.S[left:mid]
	//a.R = a.S[mid:right]

	// midはleftのendなので、rightのbegin
	copy(a.L, a.S[left:mid])
	copy(a.R, a.S[mid:right])

	a.L[mid-left] = SENTINEL
	a.R[right-mid] = SENTINEL

	j, k := 0, 0
	for i := left; i < right; i++ {
		a.compareCount++
		// SENTINELをおいて
		// ここで、Lの末尾のときRのSENTINELと比較されるようにするところが肝
		if a.L[j] < a.R[k] {
			a.S[i] = a.L[j]
			j++
		} else {
			a.S[i] = a.R[k]
			k++
		}
	}
}



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

int main() {
  double x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  
  double sum = sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
  printf("%lf\n", sum);
      
}



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

int main(void){

    int N, K;
    cin >> N;
    cin >> K;

    int num = 1;
    for(int i = 0; i < N; i++){
        if(num * 2 < num + K){
            num = num * 2;
        } else {
            num = num + K;
        }
    }
    cout << num << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <limits>

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

using namespace std;
const int INF = numeric_limits<int>::infinity();

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

    int N, highest = 0, cnt = 0;
    cin >> N;
    rep (i, N) {
        int H;
        cin >> H;
        if (highest <= H) {
            highest = H;
            cnt++;
        }
    }
    cout << cnt << '\n';
}

Measured memory_bytes: 256
from math import factorial
n,k=[int(_) for _ in input().split()]
if n == 2 and k == 1:
    print(-1)
elif n == 2 and k == 0:
    print(1)
    print(1,2)
else:
    max = factorial(n-1)//factorial(n-3)//2
    if k > max:
        print(-1)
    else:
        cnt=max-k
        print(n+cnt-1)
        for i in range(2,n+1):
            print(1,i)
        nn=2
        while cnt > 0:
            print((nn%(n-1)+2),((nn%(n-1)+2)+((nn-2)//(n-1)-1))%(n-1)+2)
            nn+=1
            cnt-=1

Measured memory_bytes: 3640
//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int maxn=3005;
int n,m;
int f[maxn],invf[maxn];
int S[maxn][maxn];
inline int ksm(int x,int y,int MOD){
	int ans=1;
	while(y){
		if(y&1) ans=(1ll*ans*x)%MOD;
		x=(1ll*x*x)%MOD; y>>=1; 
	}
	return ans;
}
int ans=0;
inline int C(int x,int y){
	if(x<y) return 0;
	return 1ll*f[x]*invf[y]%m*invf[x-y]%m; 
}
int main(){
	scanf("%d%d",&n,&m);
	f[0]=1; for(int i=1;i<=n;i++) f[i]=1ll*f[i-1]*i%m;
	invf[0]=1; invf[n]=ksm(f[n],m-2,m);
	for(int i=n-1;i>=1;i--) invf[i]=1ll*invf[i+1]*(i+1)%m;
	S[0][0]=1; S[1][1]=1; S[1][0]=0;
	for(int i=0;i<=n;i++){
		int res=0;
		for(int k=0;k<=i;k++){
			int tmp=1;
			if(!S[i+1][k+1]) S[i+1][k+1]=(S[i][k]+1ll*(k+1)*S[i][k+1]%m)%m;
//			cout<<i+1<<' '<<k+1<<' '<<S[i+1][k+1]<<endl; 
			tmp=1ll*S[i+1][k+1]*ksm(2,(n-i)*k,m)%m;
			tmp=1ll*tmp*ksm(2,ksm(2,n-i,m-1),m)%m;
			res=(res+tmp)%m;
		}
		res=(1ll*res*C(n,i))%m;
//		cout<<res<<endl;
		if(i&1) ans=(ans-res+m)%m;
		else ans=(ans+res)%m;
	}
	printf("%d\n",ans);
	return 0;
} 

Measured memory_bytes: 31336
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main() {
	int N;
	cin >> N;
	set<char> S;
	for (int i = 0; i < N; i++) {
		string c;
		cin >> c;
		S.insert(c[0]);
	}
	if (S.size() == 3) cout << "Three" << endl;
	else cout << "Four" << endl;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    bool canDevide = true;
    int count = 0;
    while(canDevide){
        rep(i,n){
            if(a[i]%2==0) a[i] /= 2;
            else {
                canDevide = false;
                break;
            }
        }
        if(canDevide) count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
 
using namespace std;
 
int N;
 
int main() {
    //scanf("%d", &N);
    cin.tie(nullptr);
    ios::sync_with_stdio(false);  
  	cin >> N;
    int res = N;
    for (int i = 0; i <= N; i++) {
        int cc = 0;
        int t = i;
        while (t > 0) cc += t % 6, t /= 6;
        t = N - i;
        while (t > 0) cc += t % 9, t /= 9;
        if (res > cc) res = cc;
    }
    cout << res  << '\n';  
    //printf("%d\n", res);
}

Measured memory_bytes: 256
ans=0
def solve(n,left,right):
    global ans
    if n==10:
        ans=1
    else:
        if a[n]>left:
            ans=solve(n+1,a[n],right)
        if a[n]>right:
            ans=solve(n+1,left,a[n])
    return ans

n=int(input())
for _ in range(n):
    a=[int(i) for i in input().split()]
    print("YES" if solve(0,0,0) else "NO")
    ans=0

Measured memory_bytes: 7620
#include <bits/stdc++.h>
#define mdsaqib std::ios::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define all(c) (c).begin(),(c).end()
#define endl '\n'
using namespace std;

signed main(){
    mdsaqib;
    string s,t;
    cin >> s >> t;
    int n=s.size();
    int m=t.size();
    int ans=1005;
    for(int i=0;i<n-m+1;i++){
        int temp=0;
        for(int j=0;j<m;j++){
            if(s[i+j]!=t[j])temp++;
        }
        ans=min(ans,temp);
    }
    cout << ans;
}

Measured memory_bytes: 3620
#include<iostream>
#include<unordered_map>
#include<bitset>
#include<math.h>
#include<vector>
#include<set>
#include<algorithm>
#include<ctype.h>
#include<unordered_set>
#include<string>
#include<iomanip>
#include<queue>
#include<limits>
#include<map>
#include<stack>
#include<iterator>
#include<cstring>
 
#include<deque>
#define pi 3.141592653589793238
#include<chrono>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
 
typedef tree<pair<ll,ll>, null_type, less_equal<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll T = 1, i, j;
    
    //cin >> T;
    while (T--) {
        ll n, k;
        cin >> n >> k;
        vector<ll> v(n);
        for(i = 0; i < n; i++){
            cin >> v[i];
        }
        indexed_set s;
        ll time = 0;
        s.insert({0, ++time});
        ll sum = 0;
        ll ans = 0;
        //s.insert({2, 5});
        for(i = 0; i < n; i++){
            sum += v[i];
            //cout <<"#"<< s.size() << endl;
            //for(auto u : s){
            //    cout << u.ff << " " << u.ss << endl;
            //}
            ll pos = s.order_of_key({sum - k * (i + 1) + 1, 0});
            pos--;
            ll minval = (*s.find_by_order(0)).ff;
            ll maxval = (*s.find_by_order(pos)).ff;
            if(maxval > sum - k * (i + 1)){
                pos--;
            }
            //cout << "####" << pos << endl;
            if(sum - k * (i + 1) >= minval)
                ans += (pos + 1);
            s.insert({sum - k * (i + 1), ++time});
            //cout <<"$$"<<ans << endl;
        }
        cout << ans;
    }
    return 0;
}

Measured memory_bytes: 17192
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBUG
const int inf=1e9+7;

int main(){
    int n,a,b,c;cin>>n>>a>>b>>c;
    vin l(n);
    rep(i,n)cin>>l[i];
    int min=inf;
    rep(i,1<<16){
        bitset<16> tmp(i);
        int suma=0;int sumb=0;int sumc=0;
        int faca=0;int facb=0;int facc=0;
        int sum=0;
        for(int j=0;j<16;j+=2){
            if(tmp[j]==0&&tmp[j+1]==0){
                suma+=l[j/2];
                faca++;
            }
            else if(tmp[j]==0&&tmp[j+1]==1){
                sumb+=l[j/2];
                facb++;
            }
            else if(tmp[j]==1&&tmp[j+1]==0){
                sumc+=l[j/2];
                facc++;
            }
        }
        if(!faca||!facb||!facc)continue;
        sum=10*(faca+facb+facc-3)+abs(a-suma)+abs(b-sumb)+abs(c-sumc);
        if(sum<min)min=sum;
    }
    cout<<min<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
int main() {
	int n,k;
	cin >> n >> k;
	int h[n],dp[n]{};
	for(int i=0;i<n;i++){
		cin >> h[i];
	}
	for(int i=0;i<n;i++){
		for(int j=i-1;j>=max(0,i-k);j--){
			if(i==j+1) dp[i]=dp[j]+abs(h[i]-h[j]);
			dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
		}
	}
	cout << dp[n-1] << endl;
}

Measured memory_bytes: 4400
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
typedef pair<int, int> P;

void solve()
{
	int n, m;
	while(cin >> n >> m, n || m)
	{
		vector< vector<int> > input(n, vector<int>(m));
		for(int i = 0; i < n; ++i)
		{
			for(int j = 0; j < m; ++j)
			{
				cin >> input[i][j];
			}
		}
		vector<int> total;
		for(int i = 0; i < m; ++i)
		{
			int sum = 0;
			for(int j = 0; j < n; ++j)
			{
				sum += input[j][i];
			}
			total.push_back(sum);
		}
		vector<int> desc = total;
		sort(desc.begin(), desc.end(), greater<int>());
		vector<int> ans;
		for(int i = 0; i < m; ++i)
		{
			int count = 0;
			for(int j = 0; j < m; ++j)
			{
				if(desc[i] == total[j])
				{
					ans.push_back(j + 1);
					++count;
				}
			}
			i += count - 1;
		}
		for(int i = 0; i < ans.size() - 1; ++i)
		{
			cout << ans[i] << " ";
		}
		cout << ans[ans.size() - 1] << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1600
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define Graph vector<vector<int>>
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

string dogname(ll N){
    ll len = 0, name = 1;
    while(len * 26 + 26 < N){
        len = len * 26 + 26;
        name++;
    }
    N -= len;
    N--;

    string S;
    rep(i, name){
        S += char('a' + (N % 26));
        N /= 26;
    }
    reverse(all(S));
    return S;
}

int main(){
    ll N;
    cin >> N;
    cout << dogname(N) << endl;
}

Measured memory_bytes: 3608
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(void)
{
	int a, b, c, i;
	char s[12];
	int len;
	c = scanf("%d %d", &a, &b);
	c = scanf("%s", s);
	len = strlen(s);
	if(len != a + b + 1){
		printf("No");
		exit(0);
	}
	else{
		for(i = 0; i < len; i++){
			if(i == a){
				if(s[i] != '-'){
					printf("No");
					exit(0);
				}
			}
			else{
				if(s[i] == '-'){
					printf("No");
					exit(0);
				}
			}
		}
		printf("Yes");
	}
	return 0;
}


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

int main()
{
	int h,n;
	cin>>h>>n;
	int x,sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		sum+=x;
	}
	if(sum>=h) cout<<"Yes"<<endl;
	else       cout<<"No"<<endl;
	return 0;
}


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

using namespace std;

typedef long long ll;

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

	int max_n = 86;
	ll lucas[max_n+1];
	lucas[0] = 2;
	lucas[1] = 1;
	for(int i = 2; i <= max_n; i++){
		lucas[i] = lucas[i - 1] + lucas[i - 2]; 
	}

	int n;
	cin >> n;

	cout << lucas[n] << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  std::string s; std::cin >> s;
  long long ret = 0, cnt = 0;
  std::for_each(s.begin(), s.end(), [&ret, &cnt] (auto c) mutable {
    if (c == 'B') cnt++;
    else ret += cnt;
  });
  std::cout << ret << std::endl;
  return 0;
}

Measured memory_bytes: 720
n = int(input())
a = [int(x) for x in input().split()]
for i in range(1, n+1):
    a[i-1] -= i 
a.sort()
b = n // 2
if n % 2 == 1:
    b = a[n//2]
else:
    b = (a[n//2] + a[n//2 - 1])//2
ans = 0
for x in a:
    ans += abs(x - b)
print(ans)

Measured memory_bytes: 88540
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
#define pb(n,m) n.push_back(m)
#define pii pair<int,int>
using namespace std;
//using bint=boost::multiprecision::cpp_int;
typedef long long ll;
typedef unsigned long long ull;

int main(){
  int c=0;
  while(1){
    c++;
    int a;
    cin>>a;
    if(!a) break;
    co("Case "<<c<<": "<<a);
  }
  return 0;
}


Measured memory_bytes: 3072
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;

struct edge{
  int n,c;
  edge(int n=0, int c=0):n(n),c(c){}
};

struct state{
  int n,c,cap;
  state(int n=0, int c=0, int cap=0):n(n),c(c),cap(cap){}
  bool operator < (const state &s) const {
    return c > s.c;
  }
};

const int INF = 1 << 29;
bool lpg[6000];
int n,m,cap,cnt,d[6000][2001],goal;
map<string,int> mp;
vector<edge> G[6000];

void init(){
  cnt = 0;
  mp.clear();
  for(int i=0;i<6000;i++) G[i].clear();
  fill(lpg,lpg+6000,false);
  fill(d[0],d[6000],INF);
}

void solve(){
  priority_queue<state> Q;
  state u(0,0,cap),v;
  d[0][cap] = 0;

  for(Q.push(u);!Q.empty();){
    u = Q.top();
    Q.pop();
    //cout << u.n << ' ' << u.c << ' ' << u.cap << endl;

    if(u.n == goal){
      cout << u.c << endl;
      return;
    } else if(u.c > d[u.n][u.cap]) continue;

    for(int i=0;i<G[u.n].size();i++){
      v = state(G[u.n][i].n, u.c+G[u.n][i].c, u.cap-G[u.n][i].c);
      if(v.cap >= 0 && v.c < d[v.n][v.cap]){
        if(lpg[v.n]) v.cap = cap;
        for(int j=v.cap;j>=0;j--) d[v.n][j] = min(d[v.n][j],v.c);
        Q.push(v);
      }
    }
  }
  cout << -1 << endl;
}

int main(){
  while(cin >> n >> m >> cap && (n|m|cap)){
    string str,str2;
    init();
    cin >> str >> str2;
    mp[str] = cnt++;
    if(mp.find(str2) == mp.end()) mp[str2] = cnt++;
    goal = mp[str2];
    cap *= 10;

    for(int i=0;i<n;i++){
      int c;
      cin >> str >> str2 >> c;
      if(mp.find(str) == mp.end()) mp[str] = cnt++;
      if(mp.find(str2) == mp.end()) mp[str2] = cnt++;
      //cout << mp[str] << ' ' << mp[str2] << ' ' << c << endl;
      G[mp[str]].push_back(edge(mp[str2],c));
      G[mp[str2]].push_back(edge(mp[str],c));
    }

    for(int i=0;i<m;i++){
      cin >> str;
      lpg[mp[str]] = true;
    }

    /*
for(int i=0;i<6;i++){
      for(int j=0;j<G[i].size();j++) cout << i << " -> " << G[i][j].n << " : " << G[i][j].c << endl;
    }
    */

    solve();
  }
}

Measured memory_bytes: 56176
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N,K; cin>>N>>K;
    vint cnt(110000,0);
    REP(i,N){
        int a,b; cin>>a>>b;
        cnt[a]+=b;
    }
    
    int cur=0;
    for(int i=1;i<110000;i++){
        cur+=cnt[i];
        if(cur>=K){
            cout<<i<<endl;
            return 0;
        }
    }
}


Measured memory_bytes: 1280
#include "bits/stdc++.h"
using namespace std;
int main() {
	string S, T;
	cin >> S >> T;
	if (S.size() < T.size()) {
		cout << "LESS" << endl;
	}
	else if (S.size() > T.size()) {
		cout << "GREATER" << endl;
	}
	else {
		if (S < T) {
			cout << "LESS" << endl;
		}
		else if (S > T) {
			cout << "GREATER" << endl;
		}
		else cout << "EQUAL" << endl;
	}
}

Measured memory_bytes: 256
#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mp make_pair
#define ALL(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
template <class T1, class T2>inline void gmax(T1 &a,T2 b){if (b>a) a=b;}
template <class T1, class T2>inline void gmin(T1 &a,T2 b){if (b<a) a=b;}
void up(int&x,int y){x+=y;if(x>=P)x-=P;}
/*ll x,y;
int main(){
    read(x),read(y);
    if (x<y) cout<<x<<endl;
    else{
        if (x%y==0) cout<<-1<<endl;
        else cout<<x<<endl;
    }
    return 0;
}*/
/*const int N=10000+10;
ll n,i,a[N],b[N],tga[N],tgb[N];
int main(){
    read(n);
    for (i=1;i<=n;i++) read(a[i]);
    for (i=1;i<=n;i++) read(b[i]);
    ll tmp=0;
    for (i=1;i<=n;i++){
        if (a[i]>b[i]) tmp+=(a[i]-b[i])*2;
    }
    for (i=1;i<=n;i++){
        if (a[i]<b[i]) tmp-=((b[i]-a[i])&1)?(b[i]-a[i]-1):(b[i]-a[i]);
    }
    puts(tmp<=0?"Yes":"No");
    return 0;
}*/
const int N=100000+10;
int n,m,i,j,x,y,sz,cnt;
ll a[N],ans;
vector<int>G[N],v[N],res;
bool vis[N];
void dfs(int x){
    vis[x]=true;
    v[cnt].pb(a[x]);
    for (int i=0;i<(int)G[x].size();i++){
        int u=G[x][i];
        if (!vis[u]) dfs(u);
    }
}
int main(){
    sz=read(n),read(m);
    for (i=1;i<=n;i++){
        read(a[i]);
    }
    for (i=1;i<=m;i++){
        read(x),read(y);
        x++,y++;
        G[x].pb(y);
        G[y].pb(x);
    }
    if (n<2*(n-m-1)) return puts("Impossible"),0;
    for (i=1;i<=n;i++)if(!vis[i]){
        cnt++;
        dfs(i);
        sort(ALL(v[cnt]));
        ans+=v[cnt][0];
        for (j=1;j<(int)v[cnt].size();j++) res.pb(v[cnt][j]);
    }
    if (cnt==1) return puts("0"),0;
    sz=n-m;
    sort(ALL(res));
    for (i=0;i<sz-2;i++) ans+=res[i];
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 10108
n = int(input())
Ratio = [list(map(int,input().split())) for _ in range(n)]
t,a = 1,1

for i in range(n):
    x = max((t+Ratio[i][0]-1)//Ratio[i][0],(a+Ratio[i][1]-1)//Ratio[i][1])
    t,a = Ratio[i][0]*x,Ratio[i][1]*x
print(int(t+a))

Measured memory_bytes: 3188
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;



#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

ll debugFlag = false;
template<typename T> void debug(T&);
template<typename T> void debug(T&, bool);
template<typename T> void debug(vector<T>&);
template<typename T> void debug(vector<T>&, bool);
template<typename T, typename U> void debug(pair<T, U>&);
template<typename T, typename U> void debug(pair<T, U>&, bool);

template<typename T>
void debug(T& obj) {
	debug(obj, true);
}

template<typename T>
void debug(T& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << obj;
	if (lnFlag) cout << endl;
}

template<typename T>
void debug(vector<T>& obj) {
	debug(obj, true);
}

template<typename T>
void debug(vector<T>& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << "[";
	rep(i, obj.size()) {
		if (i != 0) cout << ",";
		debug(obj[i], false);
	}
	cout << "]";
	if (lnFlag) cout << endl;
}

template<typename T, typename U>
void debug(pair<T, U>& obj) {
	debug(obj, true);
}

template<typename T, typename U>
void debug(pair<T, U>& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << "(";
	debug(obj.first, false);
	cout << ",";
	debug(obj.second, false);
	cout << ")";
	if (lnFlag) cout << endl;
}

void solve() {

	int A, B;
	cin >> A >> B;

	ll ans = 0;

	while (1) {

		if (ans * A - ans + 1 >= B) break;

		ans++;

	}

	cout << ans;

}


int main(int argc, char* argv[]) {
	if (argc == 2 && string(argv[1]) == "debug") debugFlag = true;
	solve();
	return 0;
}


Measured memory_bytes: 888
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();

		int[]S = new int[N+1];

		for(int i = 0 ; i < N ; i++){
			S[i] = sc.nextInt();
		}
		sc.close();

		int tmp = 2000000000;
		for(int i = 0 ; i <= N-K ; i++){
			int xl = S[i];
			int xr = S[i+K-1];


			int a = Math.abs(xr) + Math.abs(xr-xl);
			int b = Math.abs(xl) + Math.abs(xl-xr);

			if(tmp > Math.min(a, b)){
				tmp = Math.min(a, b);
			}
		}
		System.out.println(tmp);
	}
}


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

int main(){
    long long int n, m;
    cin >> n >> m;
    if(n == 1 && m == 1)cout << 1 << endl;
    else if(n == 1 || m == 1)cout << max(n,m)-2 << endl;
    else cout << n*m - (2*n + 2*(m-2)) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	int N,s,i;
	int a[100005]={0};
	while(scanf("%d",&N)!=EOF)
	{
		for(i=0;i<N;i++)
		{
			scanf("%d",&s);
			if(s==0)
			{
				a[s]++;
				a[s+1]++;
			}
			else
			{
				a[s]++;
				a[s+1]++;
				a[s-1]++;
			}
		}
		int max=0;
		for(i=0;i<=100000;i++)
			if(max<a[i]) max=a[i];
		printf("%d\n",max);
	}
	
}

Measured memory_bytes: 512
#include <stdio.h>
const int INF=7368800;
bool l[INF];
int main() {
	while(1){
		int p ,m, n,r;
		r = 0;
		for(int i=0;i< INF;++i)l[i]=false;
		scanf("%d %d", &m, &n);
		if(m==0&& n==0) break;
		p=m;
		for(int i = 0; i<n ; ++i){
		    while(l[p]){
		        ++p;
		        ++r;
		    }
		    for(int j=p; j < INF; j +=p){
		        l[j]=true;
		    }
		}
		while(l[p]){
		    ++p;
		    ++r;
		}
		printf("%d\n", r+m);
	}
    return 0;
}


Measured memory_bytes: 9816
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,found=0,count;
    cin >> n;
    while(!found)
    {
        count=0;
        for(i=2;i*i<n;i++)
        {
            if(n%i==0)
                count++;
        }
        if(count==0)
        {
            cout << n;
            break;
        }
        n++;
    }
}


Measured memory_bytes: 256
h, w = map(int, input().split())
a = [input() for _ in range(h)]
mod = 10**9+7

dp = [[0 for _ in range(w+1)] for _ in range(h+1)]
dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if i+1 < h and a[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
        if j+1 < w and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

print(dp[h-1][w-1])

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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
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; } }

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

    for(int in=0;in<s.size();in++) {
        if(in%2==0) cout << s.at(in);
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

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

    LL ct = 1;
    map<LL,LL> m;
    rep(i,N){
        m[S[i]]++;
    }
    for(auto i : m){
        LL c = i.S +1;
        ct = (ct * c) % MOD;
    }

    ct -= 1;
    cout << ct << endl;
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;
using ll = long long;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define IN(v) int v;cin>>v;
#define OUT(v) cout<<v<<endl
const ll MOD = 1e9+7;

int main() {
  IN(N);

  ll dp[101][4][4][4];
  REP(i, 101) REP(d1, 4) REP(d2, 4) REP(d3, 4)
    dp[i][d1][d2][d3] = 0;
  REP(d1, 4) REP(d2, 4) REP(d3, 4) {
    dp[3][d1][d2][d3] = 1;
  }
  dp[3][0][1][2] = 0;
  dp[3][1][0][2] = 0;
  dp[3][0][2][1] = 0;

  FOR(i, 3, N) {
    REP(d1, 4) REP(d2, 4) REP(d3, 4) {
      if ((d1 == 0 && d2 == 1 && d3 == 2) ||
          (d1 == 1 && d2 == 0 && d3 == 2) ||
          (d1 == 0 && d2 == 2 && d3 == 1))
        continue;
      REP(d, 4) {
        if ((d1 == 0 && d2 == 1 && d == 2) ||
            (d1 == 0 && d3 == 1 && d == 2) ||
            (d2 == 0 && d3 == 1 && d == 2) ||
            (d2 == 0 && d3 == 2 && d == 1) ||
            (d2 == 1 && d3 == 0 && d == 2))
          continue;

        dp[i+1][d2][d3][d] += dp[i][d1][d2][d3];
        dp[i+1][d2][d3][d] %= MOD;
      }
    }
  }
  ll ans = 0;
  REP(d1, 4) REP(d2, 4) REP(d3, 4) {
    ans += dp[N][d1][d2][d3];
    ans %= MOD;
  }
  OUT(ans);
  return 0;
}


Measured memory_bytes: 256
N,M = map(int,input().split())
Left = []
Right = []
for i in range(M):
    l,r = map(int,input().split())
    Left.append(l)
    Right.append(r)
if max(Left) > min(Right):
    print(0)
else:
    print(min(Right)-max(Left)+1)

Measured memory_bytes: 11020
#include<bits/stdc++.h>
#define forn(i, a, b) for(int i=(a); i<=(b); i++)
#define rforn(i, a, b) for(int i=(a); i>=(b); i--)
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define tests(t) int t; cin >> t; while(t--)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define gcd __gcd
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define bitcount(x) __builtin_popcount(x)
#define PI acos(-1.0)
#define mod 1000000007
#define endl '\n'
#define int ll
using namespace std;
#define N 100005
#define inf 100000000000009LL


int w[100] , v[100];
int dp[100][100001];
int32_t main()
{   
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    clock_t clk = clock();
    
    int n , W;
    cin >> n >> W;
    for(int i = 0 ; i < n ; i++){
        cin >> w[i] >> v[i];
    }
    for(int i = 0; i < 100 ; i++){
        for(int j = 0 ; j < 100001 ; j++){
            dp[i][j] = INT_MAX;
        }
    }

    dp[0][0] = 0;
    dp[0][v[0]] = w[0];

    for(int id = 1; id < n ; id++){
        dp[id][0] = 0;
        for(int j = 1; j <= 100000 ; j++){

            dp[id][j] = dp[id-1][j];
            if(j >= v[id])
            dp[id][j] = min(dp[id][j]  , w[id] + dp[id-1][j - v[id]]);

        }
    }
    int ans ;
    for(int val = 100000; val >= 0; val--){
        if(dp[n-1][val] <= W)
        {
            ans = val; break;
        }
    }

    cout << ans << endl;

    cerr<< "Time (in ms): " << double(clock() - clk) * 1000.0 / CLOCKS_PER_SEC << '\n';
}

Measured memory_bytes: 81960
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <climits>
//#include "h.h"
using namespace std;

#define ll long long
#define pint pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define pm(first, second) pb(mp(first, second))
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(X) (X).begin(), (X).end()

long int K, A, B;
int main() {
	cin >> K;
	cin >> A;
	cin >> B;
	long long int ans1 = K+1;
		long long int s = K - A + 1;
		long long int s1 = s / 2;
		long long int amari = s % 2;
		long long int ans2 = (s1 * B) - ((s1 - 1) * A) + amari;
		
	long long int k = max(ans1, ans2);
	cout << k << endl;

}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>()
        }
    };
    (;;$n:expr) => {
        {
            (0..$n).map(|_| scan!()).collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let (n, t) = scan!(usize, usize);
    let vs = scan!(i64;;);

    let mut maxs = vec![];
    let mut max = 0i64;
    for &v in vs.iter().rev() {
        if max < v {
            max = v;
        }
        maxs.push(max)
    }
    maxs = maxs.into_iter().rev().collect();

    let mut diffs = vec![];
    for (i, &v) in vs.iter().enumerate() {
        diffs.push(maxs[i] - v)
    }

    diffs.sort_by_key(|v| -v);
    let max = diffs[0];
    println!("{}", diffs.iter().filter(|&&d| d == max).count());
}


Measured memory_bytes: 10492
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
using namespace std;
vector<int> m(110,0);

int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for (int i=0; i<N; i++) cin >> d[i];
  
  for (int i=0; i<N; i++) {
    m[d[i]]++;
  }
  int count = 0;
  for (int i=1; i<=100; i++) {
    if (m[i]) {
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
using System;
class aizu{
    public static int Main(){
        int i,tmp;
        int[] n = new int[1000];
        string[] str = new string[1000];

            str = Console.ReadLine().Split(' ');
            for(i=0;i<1;i++)
                n[i] = int.Parse(str[i]);
            for(i=3;i<=n[0];i++){
                tmp = i;
                if(tmp%3==0)
                    Console.Write(" {0}",i);
                else{
                    while(tmp!=0){
                        if(tmp%10==3){
                            Console.Write(" {0}",i);
                            break;
                        }
                        tmp/=10;
                    }
                }
            }
            Console.WriteLine();       
        return 0;
    }  
}

Measured memory_bytes: 9092
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define ll long long
//map<key,value>

int main(){
  int n,k;
  cin >> n >> k;
  if(k>1)std::cout << n-k << '\n';
  else cout << "0";
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int c[30],n,k,m,a;
main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>k;
		for(int j=0;j<k;j++)cin>>a,c[a]++;
	}
	a=0;
	for(int i=0;i++<m;)a+=c[i]==n;
	cout<<a;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
const int N_MAX=100000;
int main(){
  int n,h[N_MAX+1],cnt=0,ans=0;
  cin >> n;
  cin >> h[0];
  for(int i=1;i<n;i++){
    cin >> h[i];
    if(h[i-1]>=h[i])cnt++;
    else {
      ans=max(cnt,ans);cnt=0;
    }
  }ans=max(cnt,ans);
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
function Main(input) {
	input = input.split(" ");
	
	var a = parseInt(input[0], 10);
	var b = parseInt(input[1], 10);
	var c = parseInt(input[2], 10);
    var total = a + b + c;
	
  if (total === 17) {
	console.log('YES');
  }else {
	console.log('NO');
  }
}

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

Measured memory_bytes: 7372
#include<iostream>
#include<algorithm>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int ans,f;
int n,p[111111];

int main(){
	
	cin>>n;
	rep(i,n)cin>>p[i];
	for(int i=0;i+1<n;i++){
		if(p[i]==i+1 && p[i+1]==i+2){
			swap(p[i],p[i+1]);
			ans++;
		}
	}
	rep(i,n){
		if(p[i]==i+1)ans++;
	}
	
	cout<<ans<<endl;
	
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int x,y,z;
  cin>>x>>y>>z;
  swap(x,y);
  swap(x,z);

  cout<<x<<' '<<y<<' '<<z<<newl;
  return 0;
}


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

if b == 0:
    print(0)
    exit()

m = 0
while 2**m <= b:
    m += 1
m -= 1

ans = 0
for i in range(m+1):
    qb, rb = divmod(b, 2**(i+1))
    if 0 <= rb < 2**i:
        fb = (2**i)*qb
    else:
        fb = (2**i)*qb + rb-2**i+1
    qa, ra = divmod(max(a-1, 0), 2**(i+1))
    if 0 <= ra < 2**i:
        fa = (2**i)*qa
    else:
        fa = (2**i)*qa + ra-2**i+1
    t = fb - fa
    if t%2 == 1:
        ans += 2**i

print(ans)


Measured memory_bytes: 38256
from collections import Counter
n = int(input())
li = list(map(int,input().split()))
a = [l for i,l in enumerate(li) if i % 2 == 0]
b = [l for i,l in enumerate(li) if i % 2 == 1]
se_a = list(set(a))
se_b = list(set(b))
if Counter(a).most_common()[0][0] != Counter(b).most_common()[0][0]:
    a_change = len(a) - Counter(a).most_common()[0][1]
    b_change = len(b) - Counter(b).most_common()[0][1]
    print(a_change+b_change)
else:
    if len(se_a) == 1 and len(se_b) == 1:
        print(len(a))
    else:
        x = len(a) - Counter(a).most_common()[0][1] + len(b) - Counter(b).most_common()[1][1]
        y = len(a) - Counter(a).most_common()[1][1] + len(b) - Counter(b).most_common()[0][1]
        print(min(x,y))

Measured memory_bytes: 18400
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
#define MAX 100010

signed main() {
  int n, m;
  cin >> n >> m;
  int ball[n];
  bool red[n];
  for (int i = 0; i < n; i++) {
    ball[i] = 1;
    red[i] = false;
  }
  red[0] = true;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    if (red[x - 1]) red[y - 1] = true;
    ball[x - 1]--;
    ball[y - 1]++;
    if (ball[x - 1] == 0) red[x - 1] = false;
  }
  int count = 0;
  for (int i = 0; i < n; i++) {
    if (red[i]) count++;
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;
 
int main() {
    ios::sync_with_stdio(false);
    int n, a, b = 0, z = 0;
    cin >> n;
    while (n--) cin >> a, z += a, b = max(b, a);
    cout << z - b / 2;
}


Measured memory_bytes: 256