akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main {
    private static int cnt = 0;
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int n  = sc.nextInt();
        int [] pt = new int[n];
        int [] it = new int[n];
        for(int i=0;i<n;i++) pt[i] = sc.nextInt();
        for(int i=0;i<n;i++) it[i] = sc.nextInt();
        reconstruction(0,n,0,pt,it);
        System.out.println();
    }
    public static int getindex(int [] L,int  value){
        for(int i=0;i<L.length;i++) if(L[i] == value) return i;
        return -1;
    }
    public static int  reconstruction(int l,int r,int pre_id,int [] pt,int [] it){
        if(l<r){
            int next_value = pt[pre_id++];
            int it_id = getindex(it,next_value);
            pre_id = reconstruction(l,it_id,pre_id,pt,it);
            pre_id = reconstruction(it_id+1,r,pre_id,pt,it);
            if(cnt==pt.length-1) System.out.print(next_value);
            else{
                System.out.print(next_value+" ");
                cnt++;
            }
        }
        return pre_id;
    }
}


Measured memory_bytes: 26396
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

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

int strToInt(string str)
{
	int num = 0;
	int multiple = 1;
	for(int i = str.size() - 1; i >= 0; --i)
	{
		num += (str[i] - '0') * multiple;
		multiple *= 10;
	}
	return(num);
}

void solve()
{
	string tmpStr;
	int L;
	while(true)
	{
		cin >> tmpStr;
		cin >> L;
		if(tmpStr == "0" && L == 0)
		{
			break;
		}
		int n = tmpStr.size();
		string str;
		for(int i = 0; i < L - n; ++i)
		{
			str += "0";
		}
		for(int i = 0; i < n; ++i)
		{
			str += tmpStr[i];
		}
		vector<P> pairs;
		pairs.push_back(P(strToInt(str), 0));
		int count = 0;
		bool flag = false;
		while(!flag)
		{
			++count;
			vector<char> c(L);
			for(int i = 0; i < L; ++i)
			{
				c[i] = str[i];
			}
			sort(c.begin(), c.end());
			string sMin = "";
			for(int i = 0; i < L; ++i)
			{
				sMin += c[i];
			}
			string sMax = sMin;
			reverse(sMax.begin(), sMax.end());
			int a = strToInt(sMax) - strToInt(sMin);
			for(int i = 0; i < pairs.size(); ++i)
			{
				if(pairs[i].first == a)
				{
					cout << i << " " << a << " " << count - i << endl;
					flag = true;
					break;
				}
			}
			pairs.push_back(P(a, count));
			for(int i = 0; i < L; ++i)
			{
				str[i] = a % 10 + '0';
				a /= 10;
			}
		}
	}
}

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

Measured memory_bytes: 1244
#include <stdio.h>
const int N=1e3+10;
int n,m,a[N][N],L[N][N],R[N][N],ans[N][N][2];
bool went[N][N][2];
int max(int l,int r){return l>r?l:r;}
int min(int l,int r){return l<r?l:r;}
int dp(int x,int y,bool f){
    if(went[x][y][f])return ans[x][y][f];
    ans[x][y][f]=0;
    int temp;
    if(f){
        if(x!=n){
            ans[x][y][f]=dp(x+1,y,false)+R[x+1][m]-R[x+1][y];
            went[x][y][f]=true;
        }
        if(y!=m){
            temp=dp(x,y+1,false)-L[n][y+1]+L[x][y+1];
            if(went[x][y][f])ans[x][y][f]=max(ans[x][y][f],temp);
            else ans[x][y][f]=temp;
        }
    }
    else{
        if(x!=n){
            ans[x][y][f]=dp(x+1,y,true)+R[x+1][m]-R[x+1][y];
            went[x][y][f]=true;
        }
        if(y!=m){
            temp=dp(x,y+1,true)-L[n][y+1]+L[x][y+1];
            if(went[x][y][f])ans[x][y][f]=min(ans[x][y][f],temp);
            else ans[x][y][f]=temp;
        }
    }
    went[x][y][f]=true;
    return ans[x][y][f];
}
int abs(int l){return l>0?l:-l;}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)went[i][j][0]=went[i][j][1]=L[i][j]=R[i][j]=false;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        scanf("%d",&a[i][j]);
        L[i][j]=a[i][j]+L[i-1][j];
        R[i][j]=a[i][j]+R[i][j-1];
    }
    printf("%d\n",abs(dp(0,0,true)));
}


Measured memory_bytes: 24648
def main():
    import itertools, copy
    h,w,k = map(int,input().split())
    c = []
    for i in range(h):
        c.append([])
        s = input()
        for j in range(w):
            c[i].append(s[j])
    h_stats = ((0,1) for i in range(h))
    w_stats = ((0,1) for i in range(w))
    h__ = [h_ for h_ in itertools.product(*h_stats)]
    w__ = [w_ for w_ in itertools.product(*w_stats)]
    ans = 0
    for h_ in h__:
        h_ls = []
        for i in range(len(h_)):
            if h_[i]==1:
                h_ls.append(i)
        for w_ in w__:
            w_ls = []
            for i in range(len(w_)):
                if w_[i]==1:
                    w_ls.append(i)
            c_ = copy.deepcopy(c)
            for i in range(len(h_ls)):
                for j in range(len(c_[0])):
                    c_[int(h_ls[i])][j] = '.'
            for i in range(len(w_ls)):
                for j in range(h):
                    c_[j][int(w_ls[i])] = '.'
            cnt = 0
            for i in range(h):
                for j in range(w):
                    if c_[i][j] == '#':
                        cnt += 1
            if cnt == k:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 9264
n = int(input())
a = [int(input()) for i in range(n)]
ans,flag = 0,True
if a[0]!=0: flag = False
for i in range(n-1):
	if a[i]+1==a[i+1]: ans+=1
	elif a[i]>=a[i+1]: ans+=a[i+1]
	else:
		flag = False
		break
if flag: print(ans)
else: print(-1)

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

using namespace std;
typedef pair<int, int> p;
char maze[1000][1000];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int h, w, n;
char tem[] = "S123456789";
int dis[1000][1000];
p st[10];

int bfs(p, p);

int main() {
    cin >> h >> w >> n;
    for (int i = 0; i < h; i++)
        for (int t = 0; t < w; t++) {
            cin >> maze[i][t];
            for (int j = 0; j <= n; j++) {
                if (maze[i][t] == tem[j])
                    st[j] = p(i, t);//????????
            }
        }
    int ans = 0;
    for (int i = 1; i <= n; i++) {//????
        memset(dis, -1, sizeof(dis));
        ans += bfs(st[i - 1], st[i]);
    }
    cout << ans << endl;
    return 0;
}

int bfs(p start, p ending) {
    queue<p> que;
    que.push(start);
    dis[start.first][start.second] = 0;
    while (!que.empty()) {
        p now = que.front();
        que.pop();
        if (now == ending)
            break;
        for (int i = 0; i < 4; i++) {
            int nx = now.first + dx[i];
            int ny = now.second + dy[i];
            if (nx >= 0 && nx < h && 0 <= ny && ny < w && dis[nx][ny] == -1 && maze[nx][ny] != 'X') {
                que.push(p(nx, ny));
                dis[nx][ny] = dis[now.first][now.second] + 1;
            }
        }
    }
    return dis[ending.first][ending.second];
}



Measured memory_bytes: 8020
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long a,b,c,d;
    long long sum=0;
    cin>>a>>b>>c>>d;
    sum=max({a*c,a*d,b*c,b*d,c*a,c*b,d*a,d*b});
    cout<<sum<<endl;
    return(0);
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int i,x=0;
    for(i=1;;i++){
        scanf("%d",&x);
        if(x==0){
            break;
        }
        printf("Case %d: %d\n",i,x);
    }
    return 0;
}



Measured memory_bytes: 2048
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W = map(int,readline().split())
grid = ['#']*(W+2)
for _ in range(H):
  grid += ['#'] + list(map(str,readline().decode().rstrip())) + ['X']
grid += ['#']*(W+2)
 
dist = [-1]*((H+2)*(W+2)-1)
 
s = W + 3
g = (H+1)*(W+2)-2
 
def bfs():
  while q:
    x = q.popleft()
    if x == g:
      return
    for dx in (1,W+2,-1,-W-2):
      if dist[x+dx] == -1 and grid[x+dx] =='.':
        dist[x+dx] = dist[x]+1
        q.append(x+dx)

dist[s]=0
q = deque([(s)])
bfs()

if dist[g] ==-1:
  print(-1)
else:
  print(grid.count('.')-dist[g]-1)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N, M, Q, a[50], b[50], c[50], d[50];
//---------------------------------------------------------------------------------------------------
int ans = 0;
int A[10];
void dfs(int cu = 0, int lst = 1) {
	if (cu == N) {
		int tot = 0;
		rep(i, 0, Q) if (A[b[i]] - A[a[i]] == c[i]) tot += d[i];
		chmax(ans, tot);
		return;
	}

	rep(nxt, lst, M + 1) {
		A[cu] = nxt;
		dfs(cu + 1, nxt);
	}
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M >> Q;
	rep(i, 0, Q) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		a[i]--; b[i]--;
	}

	dfs();
	cout << ans << endl;
}







Measured memory_bytes: 3640
fun main(args: Array<String>) {
    val N = readInputLine().toInt()
    
    var div = 0
    var tmp = N
    
    while (tmp != 0) {
        div += tmp % 10
        tmp /= 10
    }
    
    println(if (N % div == 0) "Yes" else "No")
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 31776
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)
#define fst first
#define snd second
#define Pqaz(T) priority_queue<T,vector<T>,greater<T>>
#define Pqza(T) priority_queue<T>
#define put(x) cout << x;
#define puts(x) cout << x << ' ';
#define putln(x) cout << x << endl;
#define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0);

void solve(void){
	int N;
	cin >> N;
	vector <int> xs(2*N);
	rep(2*N, i) {
		cin >> xs[i];
	}
	sort(all(xs));
	//putln(xs);
	int ans = 0;
	rep(2*N, i) {
		if (i & 1) continue;
		ans += xs[i];
	}
	putln(ans);
}

int main(void){
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 1e5 + 10;
int main() {
    ll h,ans=0,c=0;
    cin>>h;
    for(ll i=h;i>0;) {
        ans=ans+(pow(2,c));
        c++;
        
            i=i/2;
    }
    cout<<ans;
}


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

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

#define fill(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e18;
const ll mod = 1e9+7;
const int N = 1e3+10;

char a[N][N];
ll dp[N][N];

int main(){
fast;
int h,w;
cin>>h>>w;

for(int i=0;i<h;i++) {
    for(int j=0;j<w;j++) {
        cin>>a[i][j];
        dp[i][j]=0;
    }
}

dp[0][0]=1;
for(int i=1;i<h;i++) {
    if(a[i][0]=='#')
    break;
    dp[i][0]=1;
}

for(int i=1;i<w;i++) {
    if(a[0][i]=='#')
    break;
    dp[0][i]=1;
}

for(int i=1;i<h;i++) {
    for(int j=1;j<w;j++) {
        if(a[i][j]=='.') {
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
        }
    }
}

cout<<dp[h-1][w-1]<<endl;
return 0;
}

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

int main() {
  int N,K; cin >> N >> K;
  cout << (N % K != 0) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int maxn = 1000;

int dp[maxn][10];

void dfs(int x, int y, int k){
//	cout << x << ' ' << y << ' ' << k << endl;
	if(x == 1)return;

	for(int i = max(0,y - 1) ; i <= min(9,y + 1) ; i++){
		if(k > dp[x - 1][i]){
			k -= dp[x - 1][i];
		}
		else{
			cout << i;
			dfs(x - 1, i, k);
			break;
		}
	}
}

int main(){
	int k;cin >> k;
	for(int i = 0 ; i <= 9 ; i++)dp[1][i] = 1;
	for(int i = 2 ; dp[i - 1][1] <= k ; i++){
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][9] = dp[i - 1][9] + dp[i - 1][8];
		for(int j = 1 ; j <= 8 ; j++){
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1];
		}
	}
	bool ok = 0;
	for(int i = 1 ; !ok ;i++){
		for(int j = 1 ; !ok && j <= 9 ; j++){
			if(k > dp[i][j]){
				k -= dp[i][j];
			}
			else{
				cout << j;
				dfs(i,j,k);
				ok = 1;
			}
		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <iomanip>
#include <limits.h>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBUG = true;

int main(){

    ll x;
    cin >> x;

    ll rem = x % 100;
    ll buy = x / 100;

    if( 5 * buy >= rem){
        cout << "1" << endl;
    }
    else{
        cout << 0 << endl;
    }

}

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

using namespace std;

int main(){

	int ans = 700;
	string S;
	cin >> S;
	
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'o') {
			ans += 100;
		}

		else {
			ans += 0;
		}
	}
		cout << ans << endl;
	
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)

int main(){
    ll x;
    cin>>x;
    ll ans=0;
    ans+=(x/500)*1000;
    x%=500;
    ans+=(x/5)*5;

    cout<<ans<<endl;
}



Measured memory_bytes: 3520
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef int64_t ll;
typedef long double ld;
using namespace std;
const ll mod=1000000007;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}

int main(){
    init();
    ll N,K;cin>>N>>K;
    vector<ll>H(N);
    rep(i,N)cin>>H[i];

    sort(H.begin(),H.end(),greater<ll>());
    ll ans=0;
    rep(i,N){
      if(i<K);
      else ans+=H[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using vec = vector<ll>;
using vect = vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i, n) for (ll i = 0; i < n; i++)
#define Loop(i, m, n) for (ll i = m; i < n; i++)
#define pool(i, n) for (ll i = n; i >= 0; i--)
#define Pool(i, m, n) for (ll i = n; i >= m; i--)
#define mod 1000000007ll
#define flagcount __builtin_popcount
#define flag(x) (1 << x)
#define flagadd(bit, x) bit |= flag(x)
#define flagpop(bit, x) bit &= ~flag(x)
#define flagon(bit, i) bit &flag(i)
#define flagoff(bit, i) !(bit & (1 << i))
#define all(v) v.begin(), v.end()
#define low2way(v, x) lower_bound(all(v), x)
#define high2way(v, x) upper_bound(all(v), x)
#define idx_lower(v, x) (distance(v.begin(), low2way(v, x)))  //配列vでx未満の要素数を返す
#define idx_upper(v, x) (distance(v.begin(), high2way(v, x))) //配列vでx以下の要素数を返す
#define idx_lower2(v, x) (v.size() - idx_lower(v, x))         //配列vでx以上の要素数を返す
#define idx_upper2(v, x) (v.size() - idx_upper(v, x))         //配列vでxより大きい要素の数を返す
#define putout(a) cout << a << endl
#define Gput(a, b) G[a].push_back(b)
#define Sum(v) accumulate(all(v), 0ll)
#define gcd(x, y) __gcd(x, y)
ll ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
template <typename T>
T lcm(T x, T y)
{
    T z = gcd(x, y);
    return x * y / z;
}
template <typename T>
bool primejudge(T n)
{
    if (n < 2)
        return false;
    else if (n == 2)
        return true;
    else if (n % 2 == 0)
        return false;
    double sqrtn = sqrt(n);
    for (T i = 3; i < sqrtn + 1; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
        i++;
    }
    return true;
}
//場合によって使い分ける
//const ll dx[4]={1,0,-1,0};
//const ll dy[4]={0,1,0,-1};
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//2次元配列の宣言
//vector<vector<ll>> field(h, vector<ll>(w));

int main()
{
    cout << fixed << setprecision(30);
    ll k;
    string s;
    cin>>k>>s;
    ll siz=s.size();
    if(siz<=k)putout(s);
    else{
        loop(i,k)cout<<s[i];
        cout<<"..."<<endl;
    }
    return 0;
}


Measured memory_bytes: 3628
import java.io.File;
import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] valAry = new int[M][4];//区域  年份  case顺序  排序顺序
		
		for(int i = 0; i < M ; i++){
			int P = sc.nextInt();
			int Y = sc.nextInt();
			valAry[i][0] = P;
			valAry[i][1] = Y;
			valAry[i][2] = i;
		}
		
		Arrays.sort(valAry,new Comparator<int[]>(){
			public int compare(int[] o1, int[] o2) {
				return o1[1]-o2[1];
			}
		});
		
		int[] orderAry = new int[N+1];
		for (int i = 0; i < M; i++){
			valAry[i][3] = ++orderAry[valAry[i][0]];
		}
		
		Arrays.sort(valAry,new Comparator<int[]>(){
			public int compare(int[] o1, int[] o2) {
				return  o1[2]-o2[2];
			}
		});
		
		for(int i = 0; i < M ; i++){
			System.out.println(format(valAry[i][0])+format(valAry[i][3]));
		}
	}
	
	public static String format(int val){
		if(val > 99999) return "" + val;
		else if(val > 9999) return "0" + val;
		else if(val > 999) return "00" + val;
		else if(val > 99) return "000" + val;
		else if(val > 9) return "0000" + val;
		else if(val > 0) return "00000" + val;
		else return "";
	}
}

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

using namespace std;

int main() {
  string S;
  int last_one = -1;
  long K;
  
  cin >> S >> K;
  
  for (int i = 0; i < S.length(); i++) {
    if (S[i] == '1') {
      last_one = -1;
    }
    
    if (last_one == -1 && S[i] != '1') {
      last_one = i - 1;
      break;
    }
  }
  
  if (K - 1 <= last_one) {
    cout << 1 << endl;
  } else {
    cout << S[last_one + 1] << endl;
  }
  
  return 0;
}

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

class TEST{
	static void Main(){
		while(true){
			var s=Console.ReadLine();
			if(s==null)break;
			Sol mySol = new Sol(int.Parse(s));
			Console.WriteLine(mySol.Ans);
		}
	}
}

class Sol{
	String ans;
	public String Ans{
		get{return ans;}
	}
	
	bool[,] ARR_ADJ;
	
	int Ndomino;
	public Sol(int d){
		Ndomino=d;
		ARR_ADJ=new bool[7,7];
		for(int i=0;i<7;i++)for(int j=0;j<7;j++)ARR_ADJ[i,j]=false;
		
		var s=Console.ReadLine().Split(' ');
		for(int i=0;i<d;i++){
			ARR_ADJ[s[i][0]-'0',s[i][1]-'0']=true;
			ARR_ADJ[s[i][1]-'0',s[i][0]-'0']=true;
		}
		
		int maxlen=cal_maxlen();
		if(maxlen==Ndomino)ans="Yes";
		if(maxlen!=Ndomino)ans="No";
	}
	
	int cal_maxlen(){
		int len;
		dfs_lenmax=0;//DFS(,)のstatic local変数(として使っている)をリセット。。。
		for(int i=0;i<7;i++){
			len=0;
			DFS(i,len);
		}
		return dfs_lenmax;
	}
	
	
	int dfs_lenmax;//Cで言うstatic local変数(として使っている)
	void DFS(int now,int length){
		//Stop check;
		if(dfs_lenmax==Ndomino)return;
		int chk=0;
		for(int i=0;i<7;i++){
			if(ARR_ADJ[now,i])chk++;
		}
		if(chk==0){
			if(dfs_lenmax<length)dfs_lenmax=length;
			return;
		}
		
		//search(depth-first)
		for(int i=0;i<7;i++){
			if(ARR_ADJ[now,i]){
				ARR_ADJ[now,i]=false;
				ARR_ADJ[i,now]=false;
				DFS(i,length+1);
				ARR_ADJ[now,i]=true;
				ARR_ADJ[i,now]=true;
			}
		}
		return;
	}
}

Measured memory_bytes: 5348
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, n) for (int i = 0; i < (int)(n); i+=2)
using vi=vector<int>;  using vs=vector<string>; using gi=greater<int>;
#define soao(c) sort((c).begin(),(c).end()) //昇順
#define sodo(c) sort((c).begin(),(c).end(),gi()) //降順

int main() {
    int n,c=1; cin>>n;
    vi d(n); rep(i,n) cin>>d.at(i);
    soao(d);

    rep(i,n-1){
        if(d.at(i)<d.at(i+1)) c++;
    }
    cout<<c<<endl; 
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i, n) for(int i=0; i<n; i++)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
using namespace std;
using ll = long long;
using Graph = vector<vector<ll>>;

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

int main() {
    int N;
    cin >> N;
    ll A[N];
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    ll sum = 0;
    for (int i = 1; i < N; i++)
    {
        if(A[i-1]>A[i]){
            sum += A[i-1] - A[i];
            A[i]=A[i-1];
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 5192
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

S = raw_input()

mid = len(S) / 2
c = S[mid]
ans = mid

for i in range((len(S) + 1) / 2):
    pos1 = len(S) / 2 + i
    pos2 = (len(S) - 1) / 2 - i
    if c == S[pos1] == S[pos2]:
        ans += 1
    else:
        break

print ans

Measured memory_bytes: 4856
#include<stdio.h>
int main(void)
{
    int x,y;
    while(1)
    {
        scanf("%d %d",&x,&y);
        if(x<y)
        {
            printf("%d %d\n",x,y);
        }
        else if(x>y)
        {
            printf("%d %d\n",y,x);
        }
        else if(x==0&&y==0)break;
        else if(x==y)
        {
            printf("%d %d\n",x,y);
        }
    }
    return 0;
}

Measured memory_bytes: 2584
s = input()
n = len(s)
p = 0
for i in range(n):
    a = s[i]
    if a == 'A':
        p = i
        break
q = 0
for i in range(n):
    z = s[n-1-i]
    if z == 'Z':
        q = n-i
        break
print(q-p)
     

Measured memory_bytes: 3512
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

struct UnionFind {
    vector<int> d; // 根なら (-サイズ), そうでないなら親の番号
    UnionFind(int N) : d(N, -1){} // 全て根として初期化

    int root(int x) { // データ x が属する木の根を再帰で得る
        if (d[x] < 0) return x;
        return d[x] = root(d[x]);
    }

    bool unite(int x, int y) { // x と y の木を併合. 併合した場合 true
        x = root(x); y = root(y); // x <- x の根, y <- y の根
        if (x == y) return false; 
        // merge technique（データ構造をマージするテク. 小を大にくっつける）
        if (d[x] > d[y]) swap(x, y);    // x の木のサイズ > y の木のサイズにする. d[x], d[y] < 0 に注意.
        d[x] += d[y];   // x の木のサイズ += y の木のサイズ
        d[y] = x;   // y の親は x
        return true;
    }

    bool same(int x, int y) { // 2つのデータ x, y が属する木が同じなら true
        return root(x) == root(y);
    }
    
    int size(int x) { // 素集合のサイズ
        return -d[root(x)]; // d[root(x)] < 0 に注意.
    }
};

void Main(){
    int n, m; 
    cin >> n >> m;
    vi p(n); 
    rep(i, n) {
        cin >> p[i];
        p[i]--;
    }
    
    UnionFind UF(n);
    
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        UF.unite(a,b);
    }
    
    int cnt = 0;
    rep(i, n){
        if(UF.same(i, p[i])) cnt++;
    }
    
    cout << cnt << endl;
    return;
}

int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 4000
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
bool judge(int b1, int b2) {
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < 3; ++j) {
            if(-1 <= i - j && i - j <= 1 && ((b1 >> i) & 1) && ((b2 >> j) & 1)) {
                return false;
            }
        }
    }
    return true;
}
int main() {
    int H, N;
    cin >> H >> N;
    vector<int> X(N), Y(N);
    vector<int> f(H - 1, 7);
    for(int i = 0; i < N; ++i) {
        cin >> Y[i] >> X[i];
        if(X[i] != H - 1 && Y[i] != 3) f[X[i]] &= ~(1 << Y[i]);
        if(X[i] != H - 1 && Y[i] != 0) f[X[i]] &= ~(1 << (Y[i] - 1));
        if(X[i] != 0 && Y[i] != 3) f[X[i] - 1] &= ~(1 << Y[i]);
        if(X[i] != 0 && Y[i] != 0) f[X[i] - 1] &= ~(1 << (Y[i] - 1));
    }
    vector<int> dp(8, -inf);
    dp[0] = 0;
    for(int i = 0; i < H - 1; ++i) {
        vector<int> s = { 0, 1, 2, 4, 5 };
        vector<int> score = { 0, 1, 1, 1, 2 };
        vector<int> ndp(8, -inf);
        for(int j : s) {
            if((f[i] & j) != j) continue;
            for(int k : s) {
                if(judge(k, j)) {
                    ndp[j] = max(ndp[j], dp[k] + score[j < 4 ? j : j - 1]);
                }
            }
        }
        dp = ndp;
    }
    int ans = *max_element(dp.begin(), dp.end());
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3256
#include <stdio.h>

int s[1000000];
int main(void)
{
	int a;
	int i, j, k;
	int cnt = 0;
	
	for (i = 0; i < 1000000; i++) {
		s[i] = 1;
	}
	s[0] = 0;
	
	for (i = 2; i * i < 1000000; i++) {
		for (j = 2; i * j < 1000000; j++) {
			if (i % j == 0) {
				for (k = j; i * k < 1000000; k++) {
					 s[i * k] = 0;
				}
			}
		}
	}
	
	while (scanf("%d", &a) != EOF){
		cnt = 0;
		for (i = 2; i <= a; i++) {
			if (s[i] == 1) cnt++;
		}
		printf("%d\n", cnt);
	}
	
	return (0);
}

Measured memory_bytes: 4500
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  int H, W, h, w;
  std::cin >> H >> W >> h >> w;
  if(H%h==0&&W%w==0){
    std::cout << "No" << '\n';
    return 0;
  }
  std::cout << "Yes" << '\n';
  if(W%w!=0){
    std::vector<int> S(W+1);
    for(int i=0;i<w;i++) S[i] = 0;
    S[0] = 0;
    S[W%w] = 1000007;
    for(int i=0;i<w;i++) for(int j=i+w;j<=W;j+=w) S[j] = S[j-w] - 1;
    for(int j=0;j<H;j++) for(int i=1;i<=W;i++) std::cout << S[i] - S[i-1]<< (i==W?"\n":" ");
  }else{
    std::vector<int> S(H+1);
    for(int i=0;i<h;i++) S[i] = 0;
    S[0] = 0;
    S[H%h] = 1000007;
    for(int i=0;i<h;i++) for(int j=i+h;j<=H;j+=h) S[j] = S[j-h] - 1;
    for(int i=1;i<=H;i++) for(int j=0;j<W;j++) std::cout << S[i] - S[i-1]<< (j==W-1?"\n":" ");
  }
  return 0;
}


Measured memory_bytes: 2304
#include <map>
#include <algorithm>
#include <cassert>
#include <climits>
#include <complex>
#include <cstdio>
#include <string>
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
#define DEBUG(X) cerr<<"  "<<#X<<" = "<<X<<endl;
#define DUMP(A, n) for (auto x=begin(A); x!=begin(A)+n;x++){cout <<*x<< ' ';} cout<<endl;
#define DUMPP(A, n, m) for (auto x=begin(A); x != begin(A)+n;x++) {for (auto y=begin(*x); y != begin(*x)+m;)cout <<*y++<< ' '; cout<<endl;};
#define DUMPM(M) for (auto itr=mp.begin(); itr!=mp.end(); itr++) {cout<<itr->first<<" -> "<<itr->second<<endl;}
#define FOR(i,x,y) for(int i=(x);i<(int)(y);i++)
#define FORP(i,x,y) for(int i=(x);i<=(int)(y);i++)
#define REP(i,y) for(int i=0;i<(int)(y);i++)
#define REPP(i,y) for(int i=1;i<=(int)(y);i++)
#define RREP(i,n) for(int i=(int)(n)-1;i>=0;i--)

int main(){
	int n;
	string s;
	cin >> n >> s;
  // cntは一番多い閉じ括弧の数
	int mn = 0, cnt = 0;
	for(char c : s){
		if(c == '('){ ++cnt; }
		else{ --cnt; }
		chmin(mn, cnt);
	}
  // cout << mn << " cnt:" << cnt << endl;
	cout << string(-mn, '(') << s << string(cnt - mn, ')') << endl;
}


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

n = k()
if n== 1:
    print(0)
    sys.exit()

print(n*(n-1)//2)


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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair

int main() {
  string s,t ;
  cin >> s >> t;
  int n = s.size(), m = t.size();
  vii dp(n + 1, vi(m + 1, -inf));
  rep (i, n + 1) {
    dp[i][0] = 0;
  }
  rep (j, m + 1) {
    dp[0][j] = 0;
  }
  rep1 (i, n) {
    rep1 (j, m) {
      int add = (int)(s[i - 1] == t[j - 1]);
      dp[i][j] = max({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + add});
    }
  }
  int i = n, j = m;
  int now = dp[i][j];
  string ans;
  while (i > 0 && j > 0 && now > 0) {
    if (dp[i - 1][j - 1] + 1 == now && s[i - 1] == t[j - 1]) {
      i--;
      j--;
      ans += s[i];
      now--;
    }
    else {
      if (dp[i - 1][j - 1] == now) {
        i--; j--;
      }
      else if (dp[i - 1][j] == now) {
        i--;
      }
      else {
        j--;
      }
    }
  }
  reverse(all(ans));
  cout << ans << endl;
  
}


Measured memory_bytes: 35584
#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.at(i);
  }
  int s=0;
  int t;
  for(int i=0;i<n;i++){
    s=max(s,a.at(i));
    if(s==a.at(i)){
      t=i;
    }
  }
  int b=0;
  int c;
  for(int i=0;i<n;i++){
    if(i==t){
      continue;
    }
    b=max(b,a.at(i));
    if(b==a.at(i)){
      c=i;
    }
  }
  for(int i=0;i<n;i++){
    if(i==t){
      cout<<a.at(c)<<endl;
    }
    else{
      cout<<a.at(t)<<endl;
    }
  }
  
}



Measured memory_bytes: 2432
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, a, b; vector<int>h;

bool check(int s) {
	int c = a - b;
	vector<int>t = h;
	for (int i = 0; i < n; i++) {
		t[i] = max(0LL, t[i] - 1LL * s * b);
	}
	long long req = 0;
	for (int i = 0; i < n; i++) {
		req += (t[i] + c - 1) / c;
	}
	return req <= s;
}

int main() {
	cin >> n >> a >> b; h.resize(n);
	for (auto&& x : h)cin >> x;
	int L = 0, R = 1e9;
	while (L + 1 < R) {
		int mid = (L + R) >> 1;
		if (check(mid))R = mid; else L = mid;
	}
	cout << R << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	while(1){
		int n; cin >> n;
		if(n==0)break;
		map<char,char> mp;
		set<char> s;
		for(int i=0;i<n;i++){
			char a,b; cin >> a >> b;
			mp[a]=b;
			s.insert(a);
		}
		int m; cin >> m;
		for(int i=0;i<m;i++){
			char a; cin >> a;
			if(s.find(a)!=s.end()){
				cout << mp[a];
			}
			else{
				cout << a;
			}
		}
		cout << endl;
	}
}


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

int main(void) {
    int a, b, k;
    cin >> a >> b >> k;
    for (int i = a; i <= b; i++) {
        if (i <= a + k - 1 || b - k + 1 <= i) {
            cout << i << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef vector<int> vi;
const int inf = 1e9+7;
const int INF = 1e18+7;
int mod = 1e9+7;

int n, m;
map<P, int> d;
map<P, vector<PP> > G;

int Dijkstra(){
	priority_queue<PP, vector<PP>, greater<PP> > q;
	q.push(PP(0, P(0, -1)));
	d[P(0, -1)] = 0;
	while(!q.empty()){
		PP pp = q.top();q.pop();
		//printf("%lld %lld\n", pp.se.fi, pp.se.se);
		if(pp.fi > d[pp.se])continue;
		rep(i,G[pp.se].size()){
			PP e = G[pp.se][i];
			if(d.find(e.se) == d.end() or pp.fi+e.fi < d[e.se]){
				d[e.se] = pp.fi+e.fi;
				q.push(PP(pp.fi+e.fi, e.se));
			}
		}
	}
	return 0;
}

signed main(){
	scanf("%lld%lld", &n, &m);
	rep(i,m){
		int x, y, c;
		scanf("%lld%lld%lld", &x, &y, &c);
		x--;y--;
		G[P(x, c)].pb(PP(0, P(y, c)));
		G[P(y, c)].pb(PP(0, P(x, c)));
		G[P(x, c)].pb(PP(0, P(x, -1)));
		G[P(x, -1)].pb(PP(1, P(x, c)));
		G[P(y, c)].pb(PP(0, P(y, -1)));
		G[P(y, -1)].pb(PP(1, P(y, c)));
	}
	
	Dijkstra();
	if(d[P(n-1, -1)] == 0)printf("-1\n");
	else printf("%lld\n", d[P(n-1, -1)]);
	return 0;
}




Measured memory_bytes: 112432
#include<iostream>
#include<algorithm>
#include<cstdint>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int main() {
  int K, A, B; std::cin >> K >> A >> B;
  for(int i = A; i <= B; ++i) {
    if(i%K == 0) fin("OK");
  }
  fin("NG");
  return 0;
}


Measured memory_bytes: 3636
a, b, c, d = gets.chomp.chars.map(&:to_i)

if a + b + c + d == 7 then
    printf "%d+%d+%d+%d=7\n", a, b, c, d
elsif a - b + c + d == 7 then
    printf "%d-%d+%d+%d=7\n", a, b, c, d
elsif a + b - c + d == 7 then
    printf "%d+%d-%d+%d=7\n", a, b, c, d
elsif a + b + c - d == 7 then
    printf "%d+%d+%d-%d=7\n", a, b, c, d
elsif a - b - c + d == 7 then
    printf "%d-%d-%d+%d=7\n", a, b, c, d
elsif a + b - c - d == 7 then
    printf "%d+%d-%d-%d=7\n", a, b, c, d
elsif a - b - c - d == 7 then
    printf "%d-%d-%d-%d=7\n", a, b, c, d
elsif a - b + c - d == 7 then
    printf "%d-%d+%d-%d=7\n", a, b, c, d
end

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll a,b,c;
  cin >> a >> b >> c;
  ll mx=max({a,b,c});
  ll cnt=(mx-a)/2+(mx-b)/2+(mx-c)/2;
  ll check=(mx-a)%2+(mx-b)%2+(mx-c)%2;
  if(check==2) {
    cnt++;
  }
  else if(check==1) {
    cnt+=2;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T& t)
{T f=1;char ch=getchar();t=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')t=t*10+ch-'0',ch=getchar();t*=f;}
template <typename T,typename... Args>
inline void read(T& t, Args&... args)
{read(t);read(args...);}
int T;
int n,num[100005];
int a,b,na,nb;
int work()
{
	read(n);
	a=1e9;b=-1e9;
	for(int i=1;i<=n;i++)
	{
		read(num[i]);
		if(num[i]>n-1)return printf("No\n"),0;
		a=min(a,num[i]);b=max(b,num[i]);
	}
	if(a==b)
	{
		if(a==n-1)return printf("Yes\n"),0;
		if(n>=a*2)return printf("Yes\n"),0;
		return printf("No\n"),0;
	}
//	printf("a=%d b=%d na=%d nb=%d\n",a,b,na,nb);	
	if(a!=b-1&&a!=b)return printf("No\n"),0;
	na=nb=0; 
	for(int i=1;i<=n;i++)
		na+=num[i]==a,nb+=num[i]==b;
	if(b-na<=0)return printf("No\n"),0;
	if(nb>=(b-na)*2)return printf("Yes\n"),0;
	printf("No\n");return 0;
}
int main()
{
	work();
	return 0;
}


Measured memory_bytes: 640
#!/usr/bin/env python3
import sys


def solve(P: int, Q: int, R: int):
    print(sum([P, Q, R]) - max([P, Q, R]))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    P = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    solve(P, Q, R)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
N=int(input())

X=[]
L=[]
for i in range(N):
    x=list(map(int,input().split()))
    X.append(x)

X.sort()
Y=X[0][0]+X[0][1]

cnt=0
for i in range(1,N):
    if Y>X[i][0]-X[i][1]:
        cnt+=1
        if X[i][0]+X[i][1]<Y:
            Y=X[i][0]+X[i][1]
    else:
        Y=X[i][0]+X[i][1]

print(N-cnt)

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

int main() {
    int n, m, s, c;
    cin >> n >> m;
    vector<int> v(n, -1);
    for(int i = 0; i < m; ++i) {
        cin >> s >> c;
        s--;
        if(n != 1 && s == 0 && c == 0) {
            cout << -1 << '\n';
            return 0; 
        }
        if(v[s] == -1) v[s] = c;
        else {
            if(v[s] != c) {
                cout << -1 << '\n';
                return 0;
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        if(v[0] == -1) {
            if(n == 1) v[0] = 0;
            else v[0] = 1;
        } else if(i != 0 && v[i] == -1) v[i] = 0; 
        cout << v[i];
    }
    cout << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    int r = 0;
    for (int i = 0; i < n; ++i) {
        if(r < i*10) {
            puts("no");
            return 0;
        }
        r = max(r, i*10+v[i]);
    }
    reverse(v.begin(),v.end());
    r = 0;
    for (int i = 0; i < n; ++i) {
        if(r < i*10) {
            puts("no");
            return 0;
        }
        r = max(r, i*10+v[i]);
    }
    puts("yes");
    return 0;
}


Measured memory_bytes: 3820
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
/*answer*/
    int w, h, x, y, r;
    w = sc.nextInt();
    h = sc.nextInt();
    x = sc.nextInt();
    y = sc.nextInt();
    r = sc.nextInt();

    if(x >= r && y >= r && w >= (x + r) && h >= (y + r)){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
/*fin*/
    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 17304
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)

Mod = 10**9+7
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
def COMinit():
  #N_C_kのN
  for i in range(2, N+10):
    fac.append(fac[-1]*i%Mod)
    inv.append((-inv[Mod%i] * (Mod//i)) % Mod)
    finv.append(finv[-1] * inv[-1] % Mod)


def COM(n, k):
  if n < 0 or k < 0 or n < k:
    return 0
  return fac[n] * (finv[k] * finv[n-k] % Mod) % Mod


COMinit()
p=10**9+7

ans = 0
for i in range(N-K+1):
  j = N-1-i
  ans += A[j] * COM(j, K-1)
  ans %= p

for i in range(N-K+1):
  ans -= A[i] * COM(N-i-1, K-1)
  ans %= p

print(ans)

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

int main() {
	int N;
	int H[100000];
	cin >> N;
	for (int i = 0; i < N; i++)cin >> H[i];

	int max_cnt = 0;
	int mem = 0;
	for (int i = 0; i < N - 1; i++) {
		if (H[i] < H[i + 1])continue;
		else {
			int cnt = 0;
			for (int j = i; j < N - 1; j++) {
				if (H[j] >= H[j + 1]) cnt++;
				else {
					mem = j;
					break;
				}
				if (j == N - 2) {
					mem = j;
				}
			}
			if (cnt > max_cnt)max_cnt = cnt;
		}
		i = mem;
	}
	cout << max_cnt << endl;

	return 0;
}

Measured memory_bytes: 640
n, m = map(int, input().split())
k = []

# s[i] := i番目のスイッチについている電球群
s = [[] for _ in range(n)]
for i in range(m):
  temp = [int(i) for i in input().split()]
  k.append(temp[0])
  for j in temp[1:]:
    s[j-1].append(i)

p = [int(i) for i in input().split()]
count = 0
for i in range(2 ** n):
  state = [0 for _ in range(m)]
  for j in range(n):
    # スイッチがついていたら、つながっている電球に+1する
    if (i >> j) & 1:
      for k in s[j]:
        state[k] = (state[k] + 1) % 2
  if state == p:
    count += 1
print(count)


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

void solve(){
  int n,m;
  cin>>n>>m;
  vector<int>s(n),t(m);
  rep(i,n)cin>>s[i];
  rep(i,m)cin>>t[i];
  vector<vector<ll>>dp(n+1,vector<ll>(m+1));
  rep(i,n){
    rep(j,m){
      if(s[i]==t[j])dp[i+1][j+1]+=dp[i][j]+1;
      dp[i+1][j+1]+=dp[i][j+1]+dp[i+1][j];
      dp[i+1][j+1]%=mod;
      dp[i+1][j+1]=(dp[i+1][j+1]-dp[i][j]+mod)%mod;
    }
  }
  cout<<dp[n][m]+1<<endl;
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 31616
n = int(input())
a = list(map(int,input().split()))
dp = [[float("inf")] * (n+1) for i in range(n+1)]
rui = [0] * (n+1)
for i in range(n):
  rui[i+1] = rui[i] + a[i]
for i in range(n+1):
  for j in [-1,0,1]:
    if i + j > n:
      continue
    if i+j < 0:
      continue
    dp[i][i+j] = 0
for j in range(2,n+1):
  for i in range(n+1-j):
    for k in range(j):
      dp[i][i+j] = min(dp[i][i+k] +dp[i+k][i+j] + rui[i+j]-rui[i],dp[i][i+j])
print(dp[0][n])

Measured memory_bytes: 47708
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,a,b,c,d,i;
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	n-=1;
	long long P=b-a;
	bool flag=0;
	for (i=0;i<=n && !flag;i++)
		if (1LL*c*i-1LL*d*(n-i)<=P && P<=-1LL*c*(n-i)+1LL*d*i)
			flag=1;
	if (flag) printf("YES\n");
	else printf("NO\n");
	return 0;
}

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

ans = 0

if N[0] == 1:
    ans += 300000
elif N[0] == 2:
    ans += 200000
elif N[0] == 3:
    ans += 100000

if N[1] == 1:
    ans += 300000
elif N[1] == 2:
    ans += 200000
elif N[1] == 3:
    ans += 100000
    
if ans == 600000:
    ans += 400000


print(ans)

Measured memory_bytes: 3064
def main():
    a = [list(map(int, input().split())) for _ in range(3)]
    n = int(input())
    b = [int(input()) for _ in range(n)]
    if a[0][0] in b and a[0][1] in b and a[0][2] in b or \
        a[1][0] in b and a[1][1] in b and a[1][2] in b or \
            a[2][0] in b and a[2][1] in b and a[2][2] in b or \
                a[0][0] in b and a[1][0] in b and a[2][0] in b or \
                    a[0][1] in b and a[1][1] in b and a[2][1] in b or \
                        a[0][2] in b and a[1][2] in b and a[2][2] in b or \
                            a[0][0] in b and a[1][1] in b and a[2][2] in b or \
                                a[0][2] in b and a[1][1] in b and a[2][0] in b:
                                    print('Yes')
    else:
        print('No')
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 9268
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;

using LL = long long;

int main(void)
{
	LL a, b, c;
	cin >> a >> b >> c;
	if (a == b && a == c)
	{
		if (a % 2)
		{
			cout << 0 << endl;
			return 0;
		}
		cout << -1 << endl;
		return 0;
	}
	LL s = a + b + c;
	for(int i = 0;true;++i)
	{
		if (a % 2 || b % 2 || c % 2)
		{
			cout << i << endl;
			break;
		}
		a = s / 2 - a / 2;
		b = s / 2 - b / 2;
		c = s / 2 - c / 2;
	}
	return 0;
}


Measured memory_bytes: 256