akhauriyash/Code-Regression huggingface dataset:
# https://atcoder.jp/contests/abc156/submissions/10277689

# コンテスト中に通せたけどmodintクラスで実装してみる
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


class ModInt:
    def __init__(self, x, MOD=10 ** 9 + 7):
        self.mod = MOD
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x, self.mod)
        else:
            return ModInt(self.x + other, self.mod)

    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x, self.mod)
        else:
            return ModInt(self.x - other, self.mod)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x, self.mod)
        else:
            return ModInt(self.x * other, self.mod)

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, self.mod - 2, self.mod))
        else:
            return ModInt(self.x * pow(other, self.mod - 2, self.mod))

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, self.mod))
        else:
            return ModInt(pow(self.x, other, self.mod))

    __radd__ = __add__

    def __rsub__(self, other):  # 演算の順序が逆
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x, self.mod)
        else:
            return ModInt(other - self.x, self.mod)

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x * pow(self.x, self.mod - 2, self.mod))
        else:
            return ModInt(other * pow(self.x, self.mod - 2, self.mod))

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, self.mod))
        else:
            return ModInt(pow(other, self.x, self.mod))


def combination_mod(n, r, mod):
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


def combination(n, r):
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = ModInt(1)
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf / rf


# すべての通り(2^n-1)からnCa,nCbを引けば良い
MOD = 10**9 + 7
n, a, b = read_ints()
# tmp = pow(2, n, MOD) - 1
# ans = tmp - combination_mod(n, a, MOD) - combination_mod(n, b, MOD)
# print(ans % MOD)

tmp = ModInt(2)**n - 1
ans = tmp - combination(n, a) - combination(n, b)
print(ans)


Measured memory_bytes: 3192
#include<iostream>
 
using namespace std;
int main(){
    int N;
    cin >> N ;
    if(N < 105){
        cout << "0" << endl;
    }
    else if(N>= 105 && N < 135){
        cout << "1" << endl;
    }
    else if(N >= 135 && N < 165){
        cout << "2" << endl;
    }
 
    else if(N >= 165 && N < 189){
        cout << "3" << endl;
    }
    else if(N >= 189 && N < 195){
        cout << "4" << endl;
    }
    else{
        cout << "5" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;

struct Graph
{
    int n;
    vector<vector<int>> g;
    
    Graph(int n) : n(n){
        g.resize(n);
    }
    
    void init(int n_){
        n = n_;
        g.resize(n_);
    }
    
    void add_edge(int from, int to){
        g[from].push_back(to);
    }
};

struct Tree	//create tree(directed) from graph(undirected)
{
    int n;
    int root;
    vector<vector<int>> t;
    vector<int> par;
    vector<int> dpt;
    vector<int> tour;
    
    void init(Graph &g, int root_){
        n = g.n;
        root = root_;
        t.resize(n);
        par.resize(n);
        dpt.resize(n);
        fill(dpt.begin(), dpt.end(), -1);
        queue<int> que;
        par[root] = -1;
        dpt[root] = 0;
        que.push(root);
        while(que.size()){
            int pa = que.front();
            que.pop();
            for(int ch : g.g[pa]){
                if(dpt[ch] == -1){
                    t[pa].push_back(ch);
                    par[ch] = pa;
                    dpt[ch] = dpt[pa] + 1;
                    que.push(ch);
                }
            }
        }
    }

    Tree(){}
    
    Tree(Graph &g, int root_){
        init(g, root_);
    }
    
    vector<int> toposort(){
        typedef pair<int, int> P;
        vector<P> p(n);
        for(int i = 0; i < n; i++) p[i] = P(dpt[i], i);
        sort(p.begin(), p.end(), greater<P>());
        vector<int> res(n);
        for(int i = 0; i < n; i++) res[i] = p[i].second;
        return res;
    }

    void dfs(int u, int &k){
        tour[k] = u;
        k++;
        for(int v : t[u]){
            dfs(v, k);
            tour[k] = u;
            k++;
        }
        if(t[u].size() == 0){
            tour[k] = u;
            k++;
        }
    }
    
    int eulertour(){
        tour.resize(n * 3);
        int k = 0;
        dfs(0, k);
        return k;
    }
};

int a[200005];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    Graph g(n);
    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g.add_edge(u, v);
        g.add_edge(v, u);
    }
    Tree t(g, 0);
    int w = t.eulertour();
    int dp[200005];
    int k = 0;
    bool b[200005];
    P p[200005];
    int ans[200005];
    for(int i = 0; i < w; i++){
        int u = t.tour[i];
        if(b[u]){
            if(u == w - 1 || t.par[u] == t.tour[i + 1]){
                dp[p[u].first] = p[u].second;
                if(p[u].second == 0) k--;
            }
        }
        else{
            int l = lower_bound(dp, dp + k, a[u]) - dp;
            if(l == k) k++;
            p[u] = P(l, dp[l]);
            dp[l] = a[u];
            ans[u] = k;
            b[u] = true;
        }
    }
    for(int i = 0; i < n; i++) cout << ans[i] << endl;
}


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

int main()
{
	int m,d;
	int ans = 0;
	cin >> m >> d;
	for(int d10 = 2;d10 <= d/10;d10++){
		for(int d1 = 2;d1 <= 9;d1++){
			int t = d10*10 + d1;
			if(t > d)break;
			int month = d10 * d1;
			if(month <= m)ans ++;
			else break; 
		}
	}
	cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	private static Scanner scan;

	public static void main(String[] args) {

		scan = new Scanner(System.in);
		int i = scan.nextInt();
		int x = 1;
		while(i!=0){
			System.out.println("Case "+x+": "+i);
			x++;
			i = scan.nextInt();
		}
	}
}

Measured memory_bytes: 42944
#include<iostream>
#include<vector>
#include<stack>
#include<map>
using namespace std;

typedef vector<bool> V;
typedef pair<int,int> P;

int stoi(string x){
  int r=0;
  for(int i=0;i<x.size();i++){
    r *= 10; r += x[i]-'0';
  }
  return r;
}

inline int cal(int a,int b,string op){
  int res;
  if(op == "+")res = a+b;
  else if(op == "-")res = a-b;
  else if(op == "*")res = a*b;
  else res = a/b;
  return (res + 256) % 256;
}

int main(){
  string s,c[100];
  int m,n,a,b;
  map<string,P> h;
  V t1(256),t2(256),t3(256);


  cin >> m;
  for(int i=0;i<m;i++){
    cin >> s >> a >> b;
    h[s] = P(a,b);
  }

  cin >> n;
  for(int i=0;i<n;i++)cin >> c[i];

  stack<V> p;
  for(int i=0;i<n;i++){
    if(c[i] == "+" || c[i] == "-" || c[i] == "*" || c[i] == "/"){
      t2 = p.top(); p.pop();
      t1 = p.top(); p.pop();
      fill(t3.begin(),t3.end(),false);
      for(int j=0;j<256;j++)
	for(int k=0;k<256;k++)
	  if(t1[j] && t2[k])
	    if(!k && c[i] == "/"){
	      cout << "error\n";
	      return 0;
	    }else t3[cal(j,k,c[i])] = true;
      p.push(t3);
    }else if(h.find(c[i]) != h.end()){
      fill(t3.begin(),t3.end(),false);
      a = h[c[i]].first; b = h[c[i]].second;
      for(int j=a;j<=b;j++)t3[j] = true;
      p.push(t3);
    }else{
      fill(t3.begin(),t3.end(),false);
      t3[stoi(c[i])] = true;
      p.push(t3);
    }
  }
  cout << "correct\n";
}

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

int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        int ans = 0;
        for(int a=0;a<=9;++a)
            for(int b=0;b<=9;++b)
                for(int c=0;c<=9;++c)
                    for(int d=0;d<=9;++d)
                        if(a+b+c+d == n)
                            ++ans;
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3068
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    H, W, D = na[0], na[1], na[2]
    pos = [None] * (H * W)
    for i in range(H):
        na = list(map(int, input().split()))
        for j, a in enumerate(na):
            pos[a - 1] = (i, j)
    dist = [-1] * (H * W)
    for a in range(D):
        dist[a] = 0
    for a in range(D, H * W):
        x, y = pos[a]
        i, j = pos[a - D]
        dist[a] = dist[a - D] + abs(x - i) + abs(y - j)

    Q = int(input())
    L = []
    R = []
    for i in range(Q):
        na = list(map(int, input().split()))
        L.append(na[0])
        R.append(na[1])
    for i in range(Q):
        print(dist[R[i] - 1] - dist[L[i] - 1])


if __name__ == '__main__':
    main()



Measured memory_bytes: 22204
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
	Scanner sc =new Scanner(System.in);
	
	class T<A,B extends Comparable<B>> implements Comparable<T>{
		A first;
		B second;
		T(A f,B s){
			first = f;
			second = s;
		}
		
		@SuppressWarnings("unchecked")
		public int compareTo(T target){
			return second.compareTo((B) target.second);
		}
	}
	
	boolean type[][] ;
	int map[][];
	

	void run(){
		for(;;){
			int m = sc.nextInt();
			int n = sc.nextInt();
			if((n|m)==0){
				break;
			}
			
			type = new boolean[n][m];
			map = new int[n][m];
			
			int x = 0 ;int y = 0;
			
			for(int i = 0; i < n ; i++){
				Arrays.fill(map[i], -1);
				String buffer = sc.next();
				for(int j = 0 ; j < m;j++){
					type[i][j] = (buffer.charAt(j) != '#');

					if(buffer.charAt(j) == '&'){
						x = i;
						y = j;
					}
					
				}
			}
			
			PriorityQueue<T<T<Integer,Integer>,Integer>> q = new PriorityQueue<T<T<Integer,Integer>,Integer>>();
			
			q.add(new T<T<Integer,Integer>,Integer>(new T<Integer,Integer>(x,y),0));
			
			for(;;){
				if(q.isEmpty()){
					break;
				}
				
				T<T<Integer,Integer>,Integer> p = q.poll();
				
				if(map[p.first.first][p.first.second] != -1){
					continue;
				}
				map[p.first.first][p.first.second] = p.second;
				
				int dx[] = {1,-1,0,0};
				int dy[] = {0,0,1,-1};
				
				for(int i = 0 ; i < 4; i++){
					int ni = p.first.first + dx[i];
					int nj = p.first.second + dy[i];
					
					if(ni < 0 || nj < 0){
						continue;
					}
					if(ni >= n || nj >= m){
						continue;
					}
					if(map[ni][nj] != -1){
						continue;
					}
					

					q.add(new T<T<Integer,Integer>,Integer>(new T<Integer,Integer>(ni,nj),p.second + ((type[p.first.first][p.first.second] == type[ni][nj])?0:1)));
				}
			}
			int ans = Integer.MAX_VALUE;
			for(int i = 0 ; i < n ; i++){
				ans = Math.min(ans,map[i][0]);
				ans = Math.min(ans,map[i][m-1]);
			}

			for(int j = 0 ; j < m ; j++){
				ans = Math.min(ans,map[0][j]);
				ans = Math.min(ans,map[n-1][j]);
			}

			System.out.println((ans+1)/2);
		}
		
		
	}
	
	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}

}

Measured memory_bytes: 13000
loop do
	str = gets.chomp.to_s
	break if str == "#"
	str_tmp = str
	ss = str_tmp.chars
	left = "asdfqwerzxcvbgt"
	right = "poiuylkjhmn"
	left = left.chars
	right = right.chars
	cnt = 0
	flag = 0
	ss.each do |sss|
		left.each do |l|
			if l == sss && flag != 1
				cnt += 1
				flag = 1
			end
		end
		right.each do |r|
			if r == sss && flag != 2
				flag = 2 
				cnt += 1
			end
		end
	end
	p cnt-1
end

Measured memory_bytes: 8832
/*
* @Author Silviase(@silviasetitech)
* For ProCon
*/

import java.util.*;
import java.lang.*;
import java.math.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        String s = sc.next();
        if (s.endsWith("keyence") || (s.endsWith("eyence")&&s.startsWith("k"))
            || (s.endsWith("yence")&&s.startsWith("ke"))
            || (s.endsWith("ence")&&s.startsWith("key"))
            || (s.endsWith("nce")&&s.startsWith("keye"))
            || (s.endsWith("ce")&&s.startsWith("keyen"))
            || (s.endsWith("e")&&s.startsWith("keyenc")) ){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }

        sc.close();
    }

}

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


int main()
{
    int x;
    cin >> x;
    if(x >= 30) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3616
def number(l):
  count=0
  mini=l[0]
  for i in range(n):
    if l[i]<=mini:
      mini=l[i]
      #miniはi-1番目のうち最も小さい値であるから、これより小さかったら、i-1番目のどれよりも小さい
      count+=1
  return count

n=int(input())
p=list(map(int,input().split()))
result=number(p)
print(result)

Measured memory_bytes: 75472
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n, k = map(int, input().split())
    d = []
    a = []
    for i in range(k):
        d.append(int(input()))
        a.append(list(map(int, input().split())))
    snuke = [0] * n
    for i in range(k):
        for j in range(d[i]):
            snuke[a[i][j]-1] += 1
    ans = 0
    for i in range(n):
        if snuke[i] == 0:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Measured memory_bytes: 9828
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int ans = a*b/2;
  cout << ans <<endl;
  return 0;
}


Measured memory_bytes: 3600
#include<iostream>
using namespace std;
int a[100], b[100], hit, blow;
int main() {
	while (cin >> a[0] >> a[1] >> a[2] >> a[3] >> b[0] >> b[1] >> b[2] >> b[3]) {
		hit = 0; blow = 0;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (i == j && a[i] == b[j]) { hit++; }
				if (i != j && a[i] == b[j]) { blow++; }
			}
		}
		cout << hit << ' ' << blow << endl;
	}
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
 
#define REP(i,n)for (int i=0;i<(n);i++)
#define PB push_back
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define ll long long
using namespace std;
typedef pair<int,int> P;
 
int n;
string s[1024];
 
int rec(int a,int b,int c){
    int res=0;
    if(c) res=1;
    for(int i=a; i<n&&b<s[i].size(); i++){
        if(s[i][b]=='.')continue;
        int x=s[i][b]-'0';
        if(s[i][b]=='*') x=rec(i+1,b+1,1);
        if(s[i][b]=='+') x=rec(i+1,b+1,0);
        if(c)res*=x;
        else res+=x;
    }
    return res;
}
 
int main(){
    while(1){
        cin>>n;
        if(n==0)break;
        REP(i,n)cin>>s[i];
        cout<<rec(0,0,0)<<endl;
    }
}


Measured memory_bytes: 3080
/* AOJ My Practice
 * author: Leonardone @ NEETSDKASU
 */
#include <stdio.h>

int ws[100000] = {0};

int main(void) {
    int n, k, w, i, mx = 0, sum = 0;
    scanf("%d %d", &n, &k);
    if (k > n) { k = n; }
    for (i = 0; i < n; i++) {
        scanf("%d", &w);
        ws[i] = w;
        sum += w;
        if (w > mx) { mx = w; }
    }
    sum = (sum + k - 1) / k;
    if (sum > mx) { mx = sum; }
    w = mx * k;
    while (mx < w) {
        i = (w - mx) / 2 + mx;
        int j, e = k;
        sum = 0;
        for (j = 0; j < n; j++) {
            if (sum + ws[j] > i) {
                e--;
                if (e == 0) {
                    break;
                }
                sum = 0;
            }
            sum += ws[j];
        }
        if (j == n) {
            w = i;
        } else {
            mx = i + 1;
        }
    }
    printf("%d\n", mx);
    return 0;
}


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

void bubble_sort(int N, float* A){
	int nchange = 0;
	bool cont = true;

	for(int i=0; cont; i++){
		cont = false;
		//未ソート部分列のスワップが発生しない場合停止
		for(int j=N-1; j>i; j--){
			if(A[j-1] > A[j]){
				swap(A[j-1], A[j]);
				cont = true;
				nchange++;
			}
		}
	}
	
	for(int i=0; i<N; i++){
		if(i==N-1){
			cout << A[i] << endl;
		}else{
			cout << A[i] << " ";
		}
	}
	cout << nchange << endl;
}

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

	bubble_sort(N, A);
	return 0;
}


Measured memory_bytes: 3288
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
ll gcd(ll a, ll b);
int main(){
cin.tie(0);
string n;
ll result=0;
cin>>n;
for(ll i=0;i<n.length();i++){
  	//cout<<"n[i]:"<<ll(n[i])-48<<endl;
    result=(result+ll(n[i])-48)%9;
  	

}
  //cout<<result<<endl;
if(result%9==0)cout<<"Yes";
else cout<<"No";
return 0;
}






ll gcd(ll a, ll b){

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

}

Measured memory_bytes: 3716
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = int64_t;
using ull = uint64_t;

constexpr ll INF = 1000000000;/* 1e+9a */
namespace utils{

    class Repeater{
        int st;
        int ed;
        int d;
    public:
        class rep_iterator{
            int i; int d;
        public:
            rep_iterator(int x, int pd) :i(x), d(pd) {}

            int& operator*(){ return i; }
            bool operator==(const rep_iterator& k) const { return i == k.i; }
            bool operator!=(const rep_iterator& k) const { return i != k.i; }
            rep_iterator& operator++(){ i+=d; return *this; }
        };

        explicit Repeater(int N) :st(0), ed(N), d(1) {}
        Repeater(int b, int e) :st(b), ed(e), d(1) {if(st > ed){ st--; ed--; d = -1; } }

        rep_iterator begin() const{ return rep_iterator(st, d); }
        rep_iterator end() const{ return rep_iterator(ed, d); }

    };

    template<class T, class Compare> using p_queue = priority_queue<T, vector<T>, Compare>;
    template<class T> using min_queue = p_queue<T, greater<T>>;
    template<class T> using max_queue = p_queue<T, less<T>>;

    template<class T> bool min_update(T& X, const T& A){ if(X > A) {X = A; return true;} return false; }
    template<class T> bool max_update(T& X, const T& A){ if(X < A) {X = A; return true;} return false; }
#define ALL(x) begin(x), end(x)
#define rALL(x) rbegin(x), rend(x)
}
using namespace utils;


void sub_main(istream &is) {
    ll N, K;
    is >> N >> K;
    if(!is) return;
    string S;
    is >> S;
    S[K-1] = 'a' + (S[K-1] - 'A');
    cout << S << endl;

}

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef DEBUG
    string test_cases = "test_A.txt";
    cerr << "DEBUG MODE" <<  endl;
    cerr << test_cases << " -->" << endl;
    auto fs = fstream(test_cases, fstream::in);
    int lp = 0;
    while(fs) {
        lp++;
        cout << lp <<  "#------\n";
        sub_main(fs);
    }
    cout << "------#" << endl;
    if(lp <= 1) sub_main(cin);
#else
    sub_main(cin);
#endif
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>

typedef long long ll;
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    ll n,  m;
    cin >> n >> m;
    ll sum = 0;
    ll el;
    for(int i = 0; i < m; ++i){
        cin >> el;
        sum += el;
    }
    cout << max(-1ll, n-sum) << endl;
    return 0;
}




Measured memory_bytes: 3196
K = int(input())
queue = [1,2,3,4,5,6,7,8,9]
i = 0
flag = 1
while(flag==1):
    if K<len(queue):
        flag = 0
        break
    else:
        x = queue[i]
        if x%10 != 0:
            queue.append(x*10+x%10-1)
        queue.append(10*x+x%10)

        if x%10 != 9:
            queue.append(10*x+x%10+1)

    i+=1

print(queue[K-1])


Measured memory_bytes: 7196
N, L = map(int, input().split())
tmp = 100000
proper_i = 0
for i in range(N):
    i = i+1
    m = abs(L + i - 1)
    if m == 0:
        proper_i = i
        break
    elif m < tmp:
        tmp = m
        proper_i = i
apple = []
for i in range(N):
    i = i + 1
    apple.append(L + i - 1)
taste = sum(apple) - apple[proper_i - 1]
print(taste)




Measured memory_bytes: 3064
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<int> in(n * 3);
  for (int i = 0; i <  n * 3; i++) {
    cin >> in[i];
  }
  vector<long long> hi(n * 3), lo(n * 3);
  long long sum = 0;
  {
    priority_queue<int> que;
    for (int i = 0; i < n * 3; i++) {
      sum += in[i];
      que.push(-in[i]);
      if ((int) que.size() > n) {
        sum += que.top();
        que.pop();
      }
      hi[i] = sum;
    }
  }
  sum = 0;
  {
    priority_queue<int> que;
    for (int i = n * 3  - 1; i >= 0; i--) {
      sum += in[i];
      que.push(in[i]);
      if ((int) que.size() > n) {
        sum -= que.top();
        que.pop();
      }
      lo[i] = sum;
    }
  }
  long long ans = -LLONG_MAX;
  for (int i = n - 1; i < 2 * n; i++) {
    ans = max(ans, hi[i] - lo[i + 1]);
  }
  cout << ans << endl;
  return 0;	
}

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

int main() {
	int a, b;
	cin >> a >> b;
	string ans = "No";
	if (a % 2 != 0 && b % 2 != 0) {
		ans = "Yes";
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    int N; cin >> N;
    if(65 <= N && N <= 90) cout << 1 << '\n';
    else if(97 <= N && N <= 122) cout << 2 << '\n';
    else cout << 0 << '\n';
    return 0;
}



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

int main(){
    string s; cin >> s;
    int n = s.length();
    bool check = 1;
    if(s[0] != '1' || s[n-1] != '0') check = 0;
    rep(i,n/2) if(s[i] != s[n-2-i]) check = 0;
    if(check){
        int from = 1, to = 2;
        rep(i,n-1){
            if(s[i] == '1'){
                printf("%d %d\n",from,to);
                from = to; to++;
            }
            else{
                printf("%d %d\n",to,from);
                to++;
            }
        }
    }
    else printf("%d",-1);
    return 0;
}

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


class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * size
        self.rank = [1] * size
        self.groups = size

    def get_root(self, node):
        parent = self.parent[node]
        if parent == -1:
            root = node
        else:
            root = self.get_root(parent)
            self.parent[node] = root  # 同じnodeへの2回目以降のget_rootを高速にするために、直接rootに繋いでおく
        return root

    def in_same_group(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        return root1 == root2

    def unite(self, node1, node2):
        if self.in_same_group(node1, node2):
            return
        main_root = self.get_root(node1)
        sub_root = self.get_root(node2)
        if self.rank[main_root] < self.rank[sub_root]:  # rankの大きい方をmain_rootにする
            main_root, sub_root = sub_root, main_root

        self.parent[sub_root] = main_root
        self.rank[main_root] += self.rank[sub_root]
        self.groups -= 1


def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        uf.unite(a, b)

    ans = max(uf.rank)
    print(ans)


if __name__ == "__main__":
    main()


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


int main(){
    int N, Y;
    cin >> N >> Y;
    
    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            int k = (Y-(i*10000+j*5000))/1000;
            if(i*10000+j*5000+k*1000==Y){
                if(i+j+k==N && k>=0 && k<=N){
                    cout << i <<" "<< j <<" "<< k << endl;
                    return 0;
                }
            }
        }
    }
    
    cout << -1 <<" "<< -1 <<" "<< -1 << endl;
}


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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}


signed main() {
  int n, p[5001], kp[5001];
  cin >> n;

  rep(i, 0, n) cin >> p[i], kp[i] = p[i];

  int ans = 0;
  if(p[0] > p[1]) ans += p[0] - p[1], p[0] = p[1];
  rep(i, 0, n - 1) {
    if(p[i] >= 0) {
      ans += p[i] * 2;
      p[i + 1] -= p[i];
    }
  }
  if(p[n - 1] >= 0) ans += p[n - 1];

  int ans2 = 0;
  ans2 += kp[0];
  rep(i, 1, n - 1) {
    if(kp[i] >= 0) {
      ans2 += kp[i] * 2;
      kp[i + 1] -= kp[i];
    }
  }
  if(kp[n - 1] >= 0) ans2 += kp[n - 1];

  cout << min(ans, ans2) << endl;
}



Measured memory_bytes: 3204
#include <stdio.h>
int main(void) {
	long n, count = 0, i, j = 0, max;
	long h[100000], len[100000];

	scanf("%ld", &n);
	for (i = 0; i < n; i++)
		scanf("%ld", &h[i]);
	
	for (i = 0; i < n - 1; i++) {
		if (h[i] >= h[i + 1])
			count++;
		else {
			len[j] = count;
			j++;
			count = 0;
		}
	}
	len[j] = count;
	max = len[0];
	for (i = 1; i <= j; i++)
		if (max < len[i])
			max = len[i];

	printf("%ld", max);
	return 0;
}

Measured memory_bytes: 1664
#include<iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;
using ll=long long;

#define REP(i, n)  for(int i = 0; i < (int)n; ++i)
#define REP1(i, n)  for(int i = 1; i < (int)n; ++i)
#define REPMinus1(i, n)  for(int i = -1; i < (int)n; ++i)
#define REPll1(i, n)  for(ll i = 1; i*i < (int)n; ++i)

int cnt(ll n) {
    int c = 0;
    while (true) {
        if (n < 1)break;
        n = n / 10;
        c++;
    }
    return c;
}

const char alphabet[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
                           's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
const ll mod = 1e9 + 7;
const ll MAX1E5 = 100000;
const ll MAX1E10 = 10000000000;


int main() {
    int N, M, p = 0;
    ll n = 1, m = 1, answer, a0;
    cin >> N;
    vector<int> A1(N);
    vector<int> A2(N);
    cin >> n;
    a0 = n;

    fill(A1.begin(), A1.end(), -1);
    fill(A2.begin(), A2.end(), -1);

    REP1(i, N) {
        cin >> n;
        if (i % 2 == 0) {
            A1.at(i - 2) = n;
        } else {
            A2.at(i - 1) = n;
        }
    }
    if (N % 2 == 0) {
        for (int i = N - 1; 0 <= i; i--)if (A2.at(i) != -1)cout << A2.at(i) << " ";
        cout << a0 << " ";
        REP(i, N)if (A1.at(i) != -1)cout << A1.at(i) << " ";
        cout << endl;
    } else {
        for (int i = N - 1; 0 <= i; i--)if (A1.at(i) != -1)cout << A1.at(i) << " ";
        cout << a0 << " ";
        REP(i, N)if (A2.at(i) != -1)cout << A2.at(i) << " ";
        cout << endl;
    };

    return 0;

}

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

using namespace std;
//typedef long long ll;
typedef unsigned long long ll;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX;
const ll MINF = LONG_LONG_MIN;
const int INF = INT_MAX;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)

bool contain(set<char> &s, int a) { return s.find(a) != s.end(); }


//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<ll, vector<ll>, greater<ll>> PQ_ASK;
const int mod = 1000000007;


int main() {
    ll n, x;
    cin >> n >> x;
    vector<ll> boxes(n);
    rep(i, n) cin >> boxes[i];

    ll ans = 0;
    if (boxes[0] > x) {
        ans = boxes[0] - x;
        boxes[0] -= ans;
    }

    for (int i = 0; i < n - 1; i++) {
        if (boxes[i] + boxes[i + 1] > x) {
            ll now = boxes[i] + boxes[i + 1] - x;
            ans += now;
            boxes[i + 1] -= now;
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 1024
#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main(void){
	int w=0,i;
	char s[1000],b[10];
	
	scanf("%s",b);
	for(i=0;i<10;++i)b[i]=tolower(b[i]);
	while(1){
		scanf("%s",s);
		if(strcmp(s,"END_OF_TEXT")==0)break;
		for(i=0;i<1000;++i)s[i]=tolower(s[i]);
		if(strcmp(s,b)==0)w++;
	}
	printf("%d\n",w);
	return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, K;
    cin >> N >> K;
    vector<int> dest(N+1);
    for (int i = 1; i <= N; ++i) cin >> dest[i];
    if (K == 0) {
        cout << 1 << endl;
        return 0;
    }

    vector<int> path;
    vector<bool> visited(N+1, false);
    vector<int> pos(N+1);
    int i;
    for (i = 1; !visited[i]; i = dest[i]) {
        pos[i] = path.size();
        path.push_back(i);
        visited[i] = true;
    }
    int cycleStart = pos[i];
    int cycleLen = path.size() - cycleStart;

    if (K <= cycleStart) {
        cout << path[K] << endl;
    }
    else {
        K -= cycleStart;
        K %= cycleLen;
        cout << path[cycleStart + K] << endl;
    }

    return 0;
}

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

int main(void)
{
    int N, loc = 1, loop = 0, init = 0;
    long long K;
    int *A, *hist;
    scanf("%d %lld", &N, &K);
    A = (int*)malloc(sizeof(int) * (N + 1));
    hist = (int*)malloc(sizeof(int) * (N + 1));
    for (int c = 0; c < N + 1; ++c)
    {
        hist[c] = -1;
    }
    for (int c = 1; c <= N; ++c)
    {
        scanf("%d", A + c);
    }
    for (int c = 0; c < N; ++c)
    {
        hist[loc] = c;
        if (hist[A[loc]] != -1)
        {
            loop = c - hist[A[loc]] + 1;
            init = c - loop + 1;
            break;
        }
        loc = A[loc];
    }
    if (init <= K)
    {
        K -= init;
        K = K % loop;
        K += init;
    }
    loc = 1;
    for (int c = 0; c < K; ++c)
    {
        loc = A[loc];
    }
    printf("%d", loc);
    return 0;
}

Measured memory_bytes: 3300
#include <stdio.h>

int main(void) {
	int N, M;
	int answer[64] = {0};
	int i;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int a, b;
		if (scanf("%d%d", &a, &b) != 2) return 1;
		answer[a]++;
		answer[b]++;
	}
	for (i = 1; i <= N; i++) {
		printf("%d\n", answer[i]);
	}
	return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int main()
{
  int a, b; cin>>a>>b;
  int d[11][11];
  for(int i=1; i<=a; i++){
    for(int j=1; j<=b; j++){
      cin>>d[i][j];
    }
  }
  int p[11][11], q[11][11], r[11][11];
  for(int i=1; i<=a; i++){
    for(int j=1; j<=b; j++){
      bool ok=0;
      for(int k=0; k<=100; k++){
        for(int l=0; l<=100; l++){
          if(d[i][j]<k*i+l*j) continue;
          bool nuee=0;
          for(int s=1; s<=a; s++){
            for(int t=1; t<=b; t++){
              if(d[s][t]>d[i][j]+k*(s-i)+l*(t-j)){
                nuee=1;
                break;
              }
            }
            if(nuee) break;
          }
          if(!nuee){
            p[i][j]=k, q[i][j]=l, r[i][j]=d[i][j]-(k*i+l*j);
            ok=1;
            break;
          }
        }
        if(ok) break;
      }
      if(!ok){
        cout<<"Impossible"<<endl;
        return 0;
      }
    }
  }
  int n=202;
  int s=1, t=n;
  vector<P> g[205];
  set<P> st;
  int m=0;
  for(int i=1; i<=n/2-1; i++){
    g[i].push_back(P(i+1, -1)); m++;
  }
  for(int i=n/2+1; i<=n-1; i++){
    g[i].push_back(P(i+1, -2)); m++;
  }
  for(int i=1; i<=a; i++){
    for(int j=1; j<=b; j++){
      if(st.find(P(1+p[i][j], n-q[i][j]))!=st.end()) continue;
      st.insert(P(1+p[i][j], n-q[i][j]));
      g[1+p[i][j]].push_back(P(n-q[i][j], r[i][j])); m++;
    }
  }/*
  for(int i=1; i<=a; i++){
    for(int j=1; j<=b; j++){
      int dp[205];
      fill(dp+1, dp+n+1, 10000);
      dp[1]=0;
      for(int k=1; k<=n; k++){
        for(auto e:g[k]){
          if(e.second==-1) dp[e.first]=min(dp[e.first], dp[k]+i);
          else if(e.second==-2) dp[e.first]=min(dp[e.first], dp[k]+j);
          else dp[e.first]=min(dp[e.first], dp[k]+e.second);
          
        }
      }
      cout<<dp[n]<<endl;
    }
  }
  //return 0;*/
  cout<<"Possible"<<endl;
  cout<<n<<" "<<m<<endl;
  for(int i=1; i<=n; i++){
    for(auto e:g[i]){
      cout<<i<<" "<<e.first<<" ";
      if(e.second==-1) cout<<"X"<<endl;
      else if(e.second==-2) cout<<"Y"<<endl;
      else cout<<e.second<<endl;
    }
  }
  cout<<1<<" "<<n<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
struct edge {int /*from,*/to,cost;};
typedef long long ll;
typedef pair<int,int> P;
typedef pair<pair<int,int>,int> PP;
typedef vector<int> VI;
typedef vector<long long int> VL;
typedef vector<edge> VE;
//static const int INF = 2147483647;
//static const long long INF = 9223372000000000000;
//static const long long INF = 9223372000000000000/2;
//static const long long INF = 9223372000000000000/2145;
//static const int INF = 1000010000;
//static const int NIL = -1;
//static const int MOD = 1000000007;
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define np next_permutation
#define pq priority_queue
#define int ll

signed main(){
    int n;
    int a[214514];
    scanf("%lld",&n);
    int sm = 0;
    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
        sm += a[i];
    }

    int sn=a[0];
    int ar=sm-sn;
    int maxdiff = abs(sn-ar);
    for(int i=1;i<n-1;i++){
        sn += a[i];
        ar -=a[i];
        if(maxdiff>abs(sn-ar)) maxdiff=abs(sn-ar);
    }

    printf("%lld\n",maxdiff);
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;
typedef pair<int, int> P;

int d[1000001], d2[1000001];

int main()
{
	int tet[1001];
	for (int i = 1; i <= 1000; i++){
		tet[i] = i * (i + 1) * (i + 2) / 6;
	}
	
	fill(d, d + 1000001, INF);
	d[0] = 0;
	for (int i = 1; tet[i] <= 1000000; i++){
		for (int j = 0; j + tet[i] <= 1000000; j++){
			d[j + tet[i]] = min(d[j + tet[i]], d[j] + 1);
		}
	}
	
	fill(d2, d2 + 1000001, INF);
	d2[0] = 0;
	for (int i = 1; tet[i] <= 1000000; i++){
		if (tet[i] % 2 == 0) continue;
		for (int j = 0; j + tet[i] <= 1000000; j++){
			d2[j + tet[i]] = min(d2[j + tet[i]], d2[j] + 1);
		}
	}
	
	int n;
	while (scanf("%d", &n), n){
		cout << d[n] << " " << d2[n] << endl;
	}
	
	return 0;
}

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define AND(x,y,z) set_intersection((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define CONCAT(x,y) (x).insert((x).end(),(y).begin(),(y).end())
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define OR(x,y,z) set_union((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VECINT;
typedef vector<ll> VECLL;

int main() {
  int N;cin>>N;
  string S;cin>>S;
  char prevch = S[0];
  int ans = 1;
  FOR(i,1,N) {
    if (S[i]!=prevch) {
      ans++;
      prevch = S[i];
    }
  }
  OUT(ans);

  return 0;
}

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

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;
    map<string, int> s;
    for(int i = 0; i < N; i++){string a; cin >> a; s[a] += 1;}


    int max_votes = 0;
    for(auto name : s){
        chmax(max_votes, name.second);
        //cout << "key:" << name.first << " votes:" << name.second << endl;
    }

    for(auto name : s){if(max_votes == name.second){cout << name.first << endl;}}
}

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


int main() {
  int N, K;
  cin >> N >> K;
  vector<int> H(N);
  REP(i,N) {
    cin >> H[i];
  }
  sort(H.begin(), H.end());
  
  ll ans = 0;
  REP(i,N-K) {
    ans += H[i];
  }

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

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

int main(){
  vector<int> y(4,0); cin>>y[0]>>y[1]>>y[2]>>y[3];
  sort(y.begin(),y.end());
  if(y[0]=1 && y[1]==4 && y[2] ==7 && y[3]== 9) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
A, B, C = map(int, input().split())

K = int(input())
while(K > 0 and A >= B):
    B *= 2
    K -= 1

while(K > 0 and B >= C):
    C *= 2
    K -= 1

if A < B < C:
    print("Yes")

else:
    print("No")


Measured memory_bytes: 9172
n,m=list(map(int,input().split()))
pre=[[] for i in range(n)]
pre_num=[[] for i in range(n)]
city=[]

for i in range(m):
  #pの県に属してy年にできた
  p,y=map(int,input().split())
  pre[p-1].append(y)
  city.append(p-1)

from bisect import bisect_right

for i in range(n):
  town=sorted(pre[i])
  for j in range(len(town)):
    pre_num[i].append(bisect_right(town,pre[i][j]))

cnt=[0 for i in range(n)]
for i in city:
  print(str(i+1).zfill(6)+str(pre_num[i][cnt[i]]).zfill(6))
  cnt[i]+=1
  


  
  

Measured memory_bytes: 37128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main() {
    int a, b, c;
    cin >> a >> b;
    if (a + b == 3) c = 3;
    if (a + b == 4) c = 2;
    if (a + b == 5) c = 1;
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 3576
/*  -*- coding: utf-8 -*-
 *
 * d.cc: D - Line++
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 2000;

/* typedef */

typedef queue<int> qi;

/* global variables */

int ds[MAX_N], cs[MAX_N];

/* subroutines */

/* main */

int main() {
  int n, x, y;
  scanf("%d%d%d", &n, &x, &y);
  x--, y--;

  for (int st = 0; st < n; st++) {
    memset(ds, -1, sizeof(ds));
    ds[st] = 0;

    qi q;
    q.push(st);

    while (! q.empty()) {
      int u = q.front(); q.pop();
      int vd = ds[u] + 1;

      if (u > 0 && ds[u - 1] < 0)
	ds[u - 1] = vd, q.push(u - 1);
      if (u + 1 < n && ds[u + 1] < 0)
	ds[u + 1] = vd, q.push(u + 1);

      if (u == x && ds[y] < 0)
	ds[y] = vd, q.push(y);
      if (u == y && ds[x] < 0)
	ds[x] = vd, q.push(x);
    }

    for (int i = 0; i < n; i++) cs[ds[i]]++;
  }

  for (int k = 1; k < n; k++) printf("%d\n", cs[k] / 2);
  return 0;
}


Measured memory_bytes: 256
# set
h,n = gets.chomp.split(" ").map(&:to_i)
attak_arr = gets.chomp.split(" ").map(&:to_i)
sum_attak = 0

# main
0.upto(n - 1) do |i|
  sum_attak += attak_arr[i]
end

print ("Yes\n")if sum_attak >= h
print ("No\n") if sum_attak < h

Measured memory_bytes: 8708
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t x;
    cin >> x;
    int64_t res = 0;
    res += (x/500) * 1000;
    res += ((x%500) / 5) * 5;
    cout << res << endl;
}

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

long long memo[10001][101],w[101],v[101],n;

long long solve(int a,int b){
    if(b==n)return 0;
    if(memo[a][b]!=0)return memo[a][b];
    if(a-w[b]<0){memo[a][b]=solve(a,b+1);return memo[a][b];}
    else{
        memo[a][b]=max(solve(a-w[b],b+1)+v[b],solve(a,b+1));
        return memo[a][b];
    }
}

int main(void){
    int W;
    cin>>n>>W;
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i];
    }
    cout<<solve(W,0)<<endl;
    return 0;
}

Measured memory_bytes: 10964
//   PIGMEISTER™   //

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

#define ll long long
#define ull unsigned long long
#define sidha(i,x,n) for(ll i=(ll)(x);i<(ll)(n);++i)
#define ulta(i,x,n) for(ll i=(ll)(x);i>=(ll)(n);--i)
#define sab(a) a.begin(),a.end()
#define bas(a) a.rbegin(),a.rend()
#define modinv(x) powah(x,mod-2)
#define ncr(n,r) (((fact[n]*modinv(fact[n-r]))%mod*modinv(fact[r]))%mod)
#define factorial fact.pb(1);sidha(i,1,MAX)fact.pb((fact[i-1]*i)%mod)
#define test ll _;cin>>_;while(_--)
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod (ll)1000000007
//#define mod (ll)998244353
#define MAX 100005

int main()
{
    jaldi;
    
    ll n;
    cin >> n;
    ll a[n], count[n+1] = {0};
    sidha (i, 0, n-1) cin >> a[i];

    sidha (i, 0, n-1)
        count[a[i]]++;

    sidha (i, 1, n+1) cout << count[i] << '\n';

    return 0;
}


Measured memory_bytes: 6776
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    ll N; cin >> N;
    map<ll,ll> mp;
    for(int i = 0; i < N;i++){
        ll A; cin >> A; mp[A]++;
    }
    vector<pll> ps(mp.begin(),mp.end());
    sort(ps.rbegin(),ps.rend());
    
    ll h = 0,w = 0;
    for(int i = 0; i < (int)ps.size();i++){
        if(ps[i].second >= 4){
            if(h == 0) h = w = ps[i].first;
            else w = ps[i].first;
            break;
        }else if(ps[i].second >= 2){
            if(h == 0){
                h = ps[i].first;
                continue;
            }
            if(w == 0){
                w = ps[i].first;
                break;
            }
        }
    }
    res = h * w;
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}


Measured memory_bytes: 8064
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long int
#define MOD 1000000007
#define oo 1000000000000000000
#define forr(i,n) for(ll i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0) ; cout.tie(0);
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define pb push_back
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
 
using namespace __gnu_pbds; 
using namespace std;

ll valueOfIndex(ordered_set&s , ll i){ return *(s.find_by_order(i)); }
ll indexOfValue(ordered_set&s , ll x){ return s.order_of_key(x); }
ll add(ll a, ll b,ll p=MOD) { a%=p; b%=p; return (a+b + p)%p;}
ll mul(ll a, ll b,ll p=MOD) { a%=p; b%=p; return (a*b + p)%p;} // __int128
ll power(ll x,ll n,ll p=MOD){ if(x==0) return 0; if(n==0 || x==1) return 1LL;
    ll r = (power(x,n/2,p))%p; if(n&1) return mul(mul(r,r,p) , x,p); else return mul(r,r,p);
}
ll inv(ll x){return power(x,MOD-2);}


void __sol(){
    
    string a,b; cin >> a >> b;
    forr(i,a.size()){
        if(i>=b.size() || a[i]!=b[i]){
            cout << "No";
            return;
        }
    }
    cout << "Yes";
    
}


int main(){
    fastio
    ll tc=1; //cin >> tc;
    while(tc--) __sol();
    return 0;
}

Measured memory_bytes: 3624