akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
int a[105];
int n;
int check(int x){
    int ans=0;
    for(int i=1;i<=n;i++)
        ans+=((a[i]-x)*(a[i]-x));
    return ans;
}
int main(){

	cin>>n;
	int ans=1e9;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=-100;i<=100;i++){
        //cout<<check(i)<<endl;
        ans=min(ans,check(i));
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 2600
#define maxe 1100000
#define inf 99999999

int R,C,m;
int save[maxn];
char str[60][60];
int tit[maxn];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int getid(int x,int y){
	return x*C+y;
}
int net[maxn],size;
void init(){
	size=0;
	memset(net,-1,sizeof(net));
}
struct EDGE{
	int v,next;
}edge[maxe];
void add(int u,int v){
	edge[size].v=v;
	edge[size].next=net[u];
	net[u]=size++;
}

int cc,s,t;
vector<int> path[maxn];//蛟堤捩譚・逧?
bool dfs(int u,int fa){
	if(u==t) return true;
	for(int i=net[u];i!=-1;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa) continue;
		if(dfs(v,u)){
			path[cc].push_back(v);
			return true;
		}
	}
	return false;
}
int cost[60][60];
int kai[60][60],guan[60][60];
int main(){
	
	while(scanf("%d%d%d",&R,&C,&m)!=EOF){
		memset(tit,-1,sizeof(tit));
		for(int i=0;i<R;i++){
			scanf("%s",str[i]);
		}
		init();
		for(int i=0;i<R;i++){
			for(int j=0;j<C;j++){
				if(str[i][j]=='#') continue;
				for(int k=0;k<4;k++){
					int x=i+dir[k][0];
					int y=j+dir[k][1];
					if(x<0 || x>=R || y<0 || y>=C) continue;
					if(str[x][y]=='#') continue;
					add(getid(i,j), getid(x,y));
				//	add(getid(x,y), getid(i,j));
				}
			}
		}
		for(int i=0;i<R;i++){
			for(int j=0;j<C;j++){
				scanf("%d",&cost[i][j]);
			}
		}
		for(int i=0;i<R;i++){
			for(int j=0;j<C;j++){
				scanf("%d",&kai[i][j]);
			}
		}
		for(int i=0;i<R;i++){
			for(int j=0;j<C;j++){
				scanf("%d",&guan[i][j]);
			}
		}
		for(int i=1;i<=m;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			save[i]=getid(x,y);
		}
		cc=0;
		for(int i = 0 ; i < m ; i ++)path[i].clear();
		for(int i=1;i<m;i++){
			s=save[i]; t=save[i+1];
			cc++;
			dfs(s,-1);
			path[cc].push_back(s);
		}
		
		int tt = 0 ;
		int ttt = 1;
		for(int i = 1 ; i < m ; i ++) {
			int cccc = 1;
			if(i != 1)cccc ++;
			for(int j = (int)path[i].size() - cccc ; j >= 0 ; j --) {
				int idx = path[i][j];
				int rr = idx / C;
				int cc = idx % C;
				if(tit[idx] == -1) {
					tt += kai[rr][cc] + guan[rr][cc];
					tit[idx] = ttt;
				}
				else {
					tt += min(kai[rr][cc] + guan[rr][cc] , (ttt - tit[idx]) * cost[rr][cc]);
					tit[idx] = ttt;
				}
				ttt ++;
			}
		}
		printf("%d\n",tt);
	}
	return 0;
}

Measured memory_bytes: 9420
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1000000007;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	ll n;
	cin >> n;
	ll ans = 2000000000000;
	for (ll i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)
			ans = min(ans, (n / i) + i - 2);
	}
	cout << ans;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = sum(B)
for i in range(len(A) -1):
  if A[i + 1] == A[i] + 1:
    ans += C[A[i]-1]
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

vector<char> eratos(int n) {
	vector<char> is_prime(n + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i*i <= n; i++)
		if (is_prime[i]) {
			int j = i + i;
			while (j <= n) {
				is_prime[j] = false;
				j += i;
			}
		}
	return is_prime;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N=1e5+10;
  auto prime=eratos(N);
  vector<int>v(N,0);
  rep(i,0,N){
    if(prime[i]&&prime[(i+1)/2])v[i]=1;
  }
  rep(i,1,N)v[i]+=v[i-1];

  int Q; cin >> Q;
  rep(i,0,Q){
    int l, r; cin >> l >> r;
    cout<<v[r]-v[l-1]<<endl;
  }



    return 0;
}


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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP0(i, n) for (int i = (n)-1; i >= 0; --i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define RREP1(i, n) for (int i = (n); i >= 1; --i)
#define pow10(n) int(1e##n + n)

typedef long long LL;
typedef pair<int, int> P;

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0E-14;

void solve()
{
    int N;
    cin >> N;
    LL ans = 0;
    vector<LL> A(N + 1);
    REP0 (i, N)
    {
        cin >> A[i];
    }
    A[N] = 0;

    int i0 = 0;

    REP0 (i, N)
    {
        if (A[i] == 0 or i == N - 1)
        {
            FOR (j, i0, i + (i == N - 1))
            {
                ans += A[j] / 2;
                A[j + 1] += A[j] % 2;
            }
            i0 = i + 1;
        }
    }

    std::cout << ans << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(20);
    solve();
    return 0;
}


Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <functional>
#include <cstring>
#include <array>
#include <vector>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#include <complex>
#include <bitset>
#define full(c) c.begin(), c.end()
#define vector2d(name,type,h,w,init) vector<vector<type>> name(h,vector<type>(w,init)) 
const int PRIME = 1000000007;
const int INF = (int) 1e9;
const int INT_INF = 2147483647;
const long long int LL_INF = 9223372036854775807;
const double PI = acos(-1);
const double EPS = 0.00001;
typedef unsigned long long int ull;
typedef long long int ll;
using namespace std;

int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);
	int N, W;
	cin >> N >> W;
	vector<ll> dp(W + 1, -1);
	dp[0] = 0;
	for (int k = 0; k < N; k++) {
		int w, v;
		cin >> w >> v;
		for (int i = W; i >= w; i--) {
			if (dp[i - w] != -1) dp[i] = max(dp[i], dp[i - w] + v);
		}
	}
	cout << *max_element(full(dp)) << endl;
	return 0;
}


Measured memory_bytes: 1024
import java.text.SimpleDateFormat;

public class Main {
	public static void main(String args[]) {
		java.util.Scanner sc = new java.util.Scanner(System.in);
		String S = sc.next();

		boolean isYYMM = true;
		boolean isMMYY = true;

		try {
			// 日付チェック
			SimpleDateFormat sdf = new SimpleDateFormat("yyMM");
			sdf.setLenient(false);
			sdf.parse(S);

		} catch (Exception ex) {
			isYYMM = false;
		}

		try {
			// 日付チェック
			SimpleDateFormat sdf = new SimpleDateFormat("MMyy");
			sdf.setLenient(false);
			sdf.parse(S);

		} catch (Exception ex) {
			isMMYY = false;
		}

		if (isMMYY && isYYMM) {
			System.out.println("AMBIGUOUS");
		} else if (isMMYY && !isYYMM) {
			System.out.println("MMYY");
		} else if (!isMMYY && isYYMM) {
			System.out.println("YYMM");
		} else {
			System.out.println("NA");
		}

	}
}

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

// kmp をやるための前計算
vector<int> makeTable(const string& s) {
    int n = s.size();
    vector<int> ret(n+1);
    ret[0] = -1;
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && s[i] != s[j]) j = ret[j];
        ret[i+1] = ++j;
    }
    return ret;
}

// str の中に word とマッチする場所のリストを返す
// ret のそれぞれの要素 el は, 「str[el] からの文字列が word と一致する」ことを示す
vector<int> kmp(const string& str, const string& word) {
    vector<int> table = makeTable(word), ret;
    int m = 0, i = 0, n = str.size();
    while (m+i < n) {
        if (word[i] == str[m+i]) {
            if (++i == (int)(word.size())) {
                ret.push_back(m);
                m = m+i-table[i];
                i = table[i];
            }
        } else {
            m = m+i-table[i];
            if (i > 0) i = table[i];
        }
    }
    return ret;
}

int main(int argc, char const *argv[])
{
	string s,t;
	cin>>s>>t;
	int n=s.size(),m=t.size();
	s+=s;
	while (s.size()<=2*t.size())
	{
		s+=s;
	}
	vector<int> match=kmp(s,t);
	int memo[n]={},dist[n]={},ans=0;
	for (int i = 0; i < n; ++i)
	{
		if (memo[i]==1)
		{
			continue;
		}
		int now=i,nans=0;
		memo[i]=1;
		while (binary_search(match.begin(), match.end(), now))
		{
			now+=m;
			now%=n;
			++nans;
			ans=max(ans,nans);
			if (i==now)
			{
				cout<<"-1\n";
				return 0;
			}
			if (memo[now]==1)
			{
				nans+=dist[now];
				ans=max(ans,nans);
				dist[i]=nans;
				break;
			}
			memo[now]=1;
		}
		dist[i]=nans;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 15296
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        Map<Integer,Ele> map=new HashMap<>();
        int count=0;
        while (true)
        {
            String g=sc.next();
            if (g.equals("#")){break;}
            int y=sc.nextInt();
            int m=sc.nextInt();
            int d=sc.nextInt();
            if (y>31)
            {
                g="?";
                y-=30;
            }else if (y==31 && m>=5)
            {
                g="?";
                y-=30;
            }
            Ele ele=new Ele(g,y,m,d);
            map.put(count,ele);
            ++count;
        }
        for (int i:map.keySet()) { map.get(i).printEle(); }
    }
}

class Ele
{
    String gengou;
    int year;
    int mon;
    int date;

    public Ele(String g,int y,int m,int d)
    {
        gengou=g;
        year=y;
        mon=m;
        date=d;
    }

    public void printEle() { System.out.println(gengou+" "+year+" "+mon+" "+date); }
}


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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))
#define deg2rad(x) (((x)*PI) / (180.0))
#define rad2deg(x) (((x) * (180.0)) / PI)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);
template <class T> T mod(T a, T m);

int main(int argc, char* argv[]) {
  std::string S;
  std::cin >> S;

  int ans = 0;
  if ("SUN" == S) {
    ans = 7;
  } else if ("MON" == S) {
    ans = 6;
  } else if ("TUE" == S) {
    ans = 5;
  } else if ("WED" == S) {
    ans = 4;
  } else if ("THU" == S) {
    ans = 3;
  } else if ("FRI" == S) {
    ans = 2;
  } else if ("SAT" == S) {
    ans = 1;
  }

  put(ans);
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

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

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

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) { return (a * b) / gcd(a, b); }

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}

template <class T> T mod(T a, T m) { return (a % m + m) % m; }


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <set>

using namespace std;
using ll = long long;

typedef pair<ll, ll> P;

const int MOD = 1000000007;
const ll INF = 1LL << 60;


// LRUD
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
// const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

vector<vector<int> > vvi;
vector<vector<vector<int> > > vvvi;

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

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }

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

struct sort_pred {
    bool operator()(const P &left, const P &right) {
        return left.first < right.first;
    }
};

int main(int argc, char**argv){
    int a, p;
    cin >> a >> p;

    cout << (3*a + p) / 2 << endl;

    return 0;
}
















Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int N;
    long long int L[100];
    cin >> N;
    L[0] = 2;
    L[1] = 1;
    for (int i = 2; i < N+1; i++)
    {
        L[i] = L[i-1] + L[i-2];
    }
    cout << L[N] << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int A[1000000],n;

  int binarySearch(int key){
  int left=0;
  int right=n;
  int mid;
  while(left<right){
    mid=(left+right)/2;

    if(key==A[mid])
      return 1;
    else if(key<A[mid])
      right=mid;
    else left=mid+1;
  }
  return 0;
}

int main(){
  int i,q,k,sum=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);

  for(i=0;i<q;i++){
    scanf("%d",&k);
    if(binarySearch(k)==1)sum++;
  }
  printf("%d\n",sum);

  return 0;
}



Measured memory_bytes: 2104
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int perm[10];
int p[26];
int q[26];
int f[26];
int u[26];
char str[10];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<26;i++)
			p[i]=q[i]=f[i]=u[i]=0;
		for(int i=0;i<a;i++){
			scanf("%s",str);
			int len=strlen(str);
			if(len!=1)f[str[0]-'A']=1;
			int ad=1;
			for(int j=len-1;j>=0;j--){
				if(i<a-1)p[str[j]-'A']+=ad;
				else q[str[j]-'A']+=ad;
				ad*=10;
			}
		}
		int n=0;
		for(int i=0;i<26;i++)if(p[i]||q[i]){
			u[n++]=i;
		}
		//for(int i=0;i<n;i++)printf("%d ",p[u[i]]);
		for(int i=0;i<10;i++)perm[i]=0;
		for(int i=0;i<n;i++)perm[9-i]=n-i;
		int ret=0;
		do{
			bool ok=true;
			if(perm[0]&&f[u[perm[0]-1]])ok=false;
			int val=0;
			int A=0;
			for(int i=0;i<10;i++)if(perm[i]){val+=i*p[u[perm[i]-1]];A+=i*q[u[perm[i]-1]];}
			if(val!=A)ok=false;
			if(ok)ret++;
		}while(next_permutation(perm,perm+10));
		printf("%d\n",ret);
	}
}

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

int main(){
    using namespace std;
    unsigned long N;
    cin >> N;
    vector<unsigned long> A(N), B(N);
    for(auto&& i : A)cin >> i;
    inclusive_scan(begin(A), end(A), begin(B), [](auto i, auto j){return max(i, j);});
    cout << accumulate(begin(B), end(B), 0UL - accumulate(begin(A), end(A), 0UL)) << endl;
    return 0;
}

Measured memory_bytes: 6408
using System;
using System.Linq;

namespace ABC149
{
    class B
    {
        static void Main(string[] args)
        {
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long A = input[0];
            long B = input[1];
            long K = input[2];

            if (K <= A)
            {
                Console.WriteLine("{0} {1}", A - K, B);
            }
            else if (K - A <= B)
            {
                Console.WriteLine("{0} {1}", 0, B - (K - A));
            }
            else
            {
                Console.WriteLine("{0} {1}", 0, 0);
            }
        }
    }
}


Measured memory_bytes: 13396
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n) + 1; i++)
#define all(vecto) vecto.begin(),vecto.end()
typedef long long ll;

int main(){
    int n;
    cin>>n;
    bool flag = true;
    rep1(i,9){
        if(n%i==0){
            if(n/i<10){
                flag = false;
                break;
            }
        }
    }
    if(flag){
        cout << "No" << endl;
    }    
    else if(flag==false){
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int num;
    int a,b;
    int count;
    
    while(cin >> a >> b){
        count = 0;
        num = a+b;
        while(1){
            count += 1;
            num /= 10;
            if(num==0) break;
        }
        cout << count << endl;
    }
    return 0;
}



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

using namespace std;

typedef long long int lli;

int main(){
        
    lli n, res = 0, A = 0;
    cin >> n;
    
    while(n > 0){
        A += n % 10;
        n /= 10;
    }
    if(A == 1)
        cout << 10 << endl;
    else
        cout << A << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
    long long k,a,b;
    cin >> k >> a >> b;
    long long r = k-a+1;
    if((b-a)/2<1){
        cout << a+r << endl;
    }else{
        cout << (b-a)*(r/2) + r%2 + a << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

int main(){
  int a, b;
  cin >> a >> b;

  for(int i=1; i<1010; ++i){
    int x = i * 8/100;
    int y = i * 10/100;
    if(x == a && y == b){
      cout << i << endl;
      return 0;
    }
  }

  cout << -1;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

int main()
{
    int n;
    std::cin >> n;

    std::vector<int> list;
    list.reserve(n);
    int v;
    for (int i = 0; i < n; ++i) {
        std::cin >> v;
        list.push_back(v);
    }

    for (int i = 0; i < n; ++i) {
        std::cout << list[n-i-1];
        if (i == (n-1)) {
            std::cout << std::endl;
        } else {
            std::cout << " ";
        }
    }

    return 0;
}


Measured memory_bytes: 3092
//i ll be the king
#include<bits/stdc++.h>
#define ll long long int
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define rep(n) for(ll i2=0;i2<n;i2++)
#define vmp(v,a,b) v.push_back(make_pair(a,b))
#define si(a) scanf("%lld",&a)
#define pi(a) printf("%lld",a)
#define aset(a,n,k) for(ll i3=0;i3<n;i3++)a[i3]=k; 	
#define mod 1000000007
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
int main()
{
	sync;
	ll n;
	cin>>n;
	ll arr[n],pref[n+1];
	input(arr,n);
	ll dp[n+1][n+1];
	for(ll i=0;i<=n;i++)
	for(ll j=0;j<=n;j++)
	dp[i][j]=0;
	pref[0]=0;
	for(ll i=1;i<=n;i++)pref[i]=pref[i-1]+arr[i-1];
	for(ll st=2;st<=n;st++)
	{
		for(ll i=1;i<=n-st+1;i++)
		{
			ll j=i+st-1;
			dp[i][j]=1e16;
			for(ll k=i;k<=j;k++)
			dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+(pref[j]-pref[i-1]));
			
		}
	}
	cout<<dp[1][n];
}

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

using namespace std;
typedef long long ll;


int main(){
    string S; cin >> S;
    int N=S.length();
    ll sum = 0;
    for(int i=0;i<1<<(N-1);i++){ //2^N回ループ
        ll a=S[0]-'0';
        for(int j=0;j<N;j++){
            if(i&(1<<j)){ //bitが立っている->+は入らない
                a *= 10;
                a += S[j+1]-'0';
            }else{ //+が入る
                sum += a;
                a = S[j+1]-'0';
            }
        }
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int i;
  char str[16];
  
  fgets(str,sizeof(str),stdin);
  
  str[3] = '8';
  
  for(i=0;i<10;i++)
  {
    printf("%c",str[i]);
  }
  
  printf("\n");
  
  return 0;
}
    

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int A[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	cout<<A[N-1]-A[0]<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n;
char s[2][60];

int a[100];
int an;

int main()
{
	read(n);
	scanf("%s%s",s[0],s[1]);
	for(int i=0; i<n; ++i){
		if(s[0][i] == s[1][i]){
			a[++an]=1;
		} else {
			a[++an]=2;
			++i;
		}
	}
	n=an;
	ll ans=1;
	const int M=int(1e9)+7;
	if(a[1] == 2) ans=6;
	else ans=3;
	for(int i=2; i<=n; ++i){
		if(a[i-1]==1){
			if(a[i]==1){
				ans *= 2; ans %= M;
			} else {
				ans *= 2; ans %= M;
			}
		} else {
			if(a[i]==1){
				
			} else {
				ans *= 3; ans %= M;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}


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


typedef long long ll;
typedef pair<ll,int> P;

struct edge {int to; ll cost; };

int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};
 
int main(){
  int n;
  cin >> n;
  int ans = 1000-n%1000;
  if(ans==1000) ans = 0;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3600
#include "iostream"
#include "vector"
#include "iomanip"
#include "algorithm"
#include "vector"
#include "cmath"

int main() {
	long int a = 0, b = 0, c = 0, k = 0;
	std::cin >> a;
	std::cin >> b;
	std::cin >> c;
	std::cin >> k;
	if (a < k) {
		k -= a;
		if (b < k) {
			k -= b;
		}
		else {
			b = k;
			k = 0;
		}
	}
	else {
		a = k;
		b = 0;
		k = 0;
	}
	long int ans = a - k;
	std::cout << ans << std::endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int u32;
typedef pair<int, int> p;
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 Inf = (1<<30);
ll inf = (1LL<<60);
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main() {
	int n;
	cin >> n;
	int r;
	cin >> r;
	int tmp = min(n, 10);
	int hosei = 100 * (10 - tmp);
	cout << r + hosei;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
list_a = list(map(int, input().split()))
dict_a = {}
for number in list_a:
    try:
        dict_a[number] += 1
    except KeyError:
        dict_a[number] = 1
count = 0
for key,value in dict_a.items():
    if key > value:
        count += value
    else:
        count += value - key
print(count)


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

int main() {
    int n, ans, sum = 0, minv = 1001001001;
    cin >> n;
    vector<int> a(n);
    rep(i,n) {
        cin >> a[i];
        sum += a[i];
    }
    rep(i,n) {
        if (abs(sum - a[i] * n) < minv) {
            ans = i;
            minv = abs(sum - a[i] * n);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
#include<iostream>
#include<fstream>
#define ll long long
using namespace std;

vector<int> dp;
vector<vector<int>> graph;

int solve(int n){
    if(dp[n] != -1) return dp[n];
    if(graph[n].size() == 0) return dp[n] = 0;

    int res = 0;
    for(int v:graph[n]){
        dp[v] = solve(v);
        res = max(res, dp[v]+1);
    }
    return dp[n] = res;
}

int main(){
    int N, M;  cin >> N >> M;
    dp.resize(N, -1);
    graph.resize(N, vector<int>());
    for(int i=0; i<M; i++){
        int x, y;  cin >> x >> y;
        x--;  y--;
        graph[x].push_back(y);
    }

    int ans = 0;
    for(int i=0; i<N; i++){
        ans = max(ans, solve(i));
    }
    cout << ans << endl;
}


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

using namespace std;

int main()
{
   int A[3];
   cin>>A[0]>>A[1]>>A[2];
   sort(A,A+3, greater<int>());
   if(A[0]==(A[1]+A[2]))
   {
       cout<<"Yes"<<endl;
       return 0;
   }
   cout<<"No"<<endl;
   return 0;
}




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

using namespace std;
using ll=long long;

int main(){
    string s,t;
    cin>>s>>t;
    int a,b;
    cin>>a>>b;
    string u;
    cin>>u;
    if(u==s)--a;
    if(u==t)--b;
    cout<<a<<" "<<b<<endl;
    return 0;
}

Measured memory_bytes: 256
main :: IO ()
main = do
  [a, b] <-  words <$> getLine :: IO [String]
  let n = read (a ++ b)
  putStrLn $ if isSquare 0 n then "Yes" else "No"

isSquare :: Int -> Int -> Bool
isSquare i n
  | i * i > n = False
  | i * i == n = True
  | otherwise = isSquare (i + 1) n


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

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;

#define deb(x) cerr<<#x<<":"<<x<<"\n";
#define dvi(x) for(ll i=0;i<x.size();i++)cerr<<#x<<"["<<i<<"]:"<<x[i]<<" ";
#define iter(v) for(auto it:v)
#define wt ll t;cin>>t;while(t--)
#define rl(x) ll x;cin>>x;
#define rvi(x,n) vi x(n);for(ll i=0;i<n;i++) cin>>x[i];
#define rs(x) string x;cin>>x;
#define w(x) cout<<x<<endl;
#define wvi(x) for(ll i=0;i<x.size();i++) cout<<x[i]<<" ";cout<<endl;
#define ws(x) cout<<x<<endl;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ppb pop_back
#define pll pair<ll, ll>
#define fo(i,n) for(ll i=0;i<n;i++)
#define forr(i,a,b) for(ll i=a;i<b;i++)
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
const ll N = 1e9 + 7;

map<long long, long long> factorize(long long n) {	//returns map containing factor and multiplicity, Eg: 60 = {{2,2},{3,1},{5,1}}
	map<long long, long long> ans;
	for (long long i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ans[i]++;
			n /= i;
		}
	}
	if (n > 1) {
		ans[n]++;
		n = 1;
	}
	return ans;
}

void FAST() {	//FAST Input Output, DONT use both scnaf,prllf / cin,cout , Use any ONE system
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

ll powM(ll x, ll y, ll m) {	//returns (a^b)%m ( ^ is exponent )
	ll ans = 1, r = 1;
	x %= m;
	while (r > 0 && r <= y)
	{
		if (r & y)
		{
			ans *= x;
			ans %= m;
		}
		r <<= 1;
		x *= x;
		x %= m;
	}
	return ans;
} 

int main()
{
	FAST();
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
    //    freopen("output.txt", "w", stdout);
    #endif
 //   wt{
		string s;cin>>s;
		int ans=0,count=0;
		for(int i=0;i<3;i++)
		{
			if(s[i]=='R')count++;
			else count=0;
			ans=max(ans,count);
		}
		cout<<ans<<endl;
 //  }
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int m=0,e=0,ans=1;
  if(s[0]=='m')m++;
  for(int i=1;i<s.size();i++){
    if(s[i]=='m'){
      if(m+e==0)ans=0;
      m++;
    }
    if(s[i]=='e'){
      if(!m)ans=0;
      e++,m--;
    }
    if(s[i]=='w'){
      if(!e)ans=0;
      e--;
    }
  }
  if(ans&&m+e==0)cout<<"Cat"<<endl;
  else cout<<"Rabbit"<<endl;
  return 0;
}

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

int main() {
	string S, T;
	cin >> S >> T;
	vector<int> start(26, -1);
	vector<int> goal(26, -1);
	for (int i = 0; i < S.size(); i++)
	{
		int a = S[i] - 'a';
		int b = T[i] - 'a';

		if (start[a] != -1 || goal[b] != -1) {
			if (start[a] != b || goal[b] != a) {
				cout << "No" << endl;
				return 0;
			}
		}
		else {
			start[a] = b;
			goal[b] = a;
		}
	}

	cout << "Yes" << endl;
}

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

void chmin(int& a, int b) {
  if (a > b) a = b;
}

int main() {
  int N, K;
  cin >> N >> K;
  
  int ans = 1000000;
  int num;
  for (int i = 1; i <= N; i++) {
    num = ((i + K-3)/ (K-1)) + ((N - i + (K-2))/(K-1));
    
    chmin(ans, num);
   
  }
    cout << ans << endl;
  
}




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

long long a[100010];
main(){
	long long n,k,q,tmp;
	cin>>n>>k>>q;
	for(int i=1;i<=q;i++){
		cin>>tmp;
		a[tmp]++;
	}
	for(int i=1;i<=n;i++){
		a[i] += k-q;
		if(a[i] <= 0)	cout<<"No"<<endl;
		else			cout<<"Yes"<<endl;
	}
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;

const int N=2e5+5;
const ll INF = ll(1e18)+1;
ll A[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    ll k;
    cin >> n >> k;
    for(int i=0; i<n; i++) cin >> A[i];
    sort(A, A+n);

	ll lb = -INF, ub = INF;
	while(ub - lb > 1) {
		ll x = (lb + ub)/2;
		bool ok = [&] {
			ll tot = 0;
			for(int i=0; i<n; i++) {
				int l = -1, r = n;
				if(A[i] < 0) {
					// big ---------x-------> small
					//   l ------c----------> r
					while(r - l > 1) {
						int c = ( l+r )/2;
						if( A[c]*A[i]<x ) r = c;
						else l = c;
					}
					tot += n - r;
				} else {
					// small ---------x-------> big
					//     l ------c----------> r
					while( r-l > 1) {
						int c = ( l+r )/2;
						if( A[c]*A[i]<x ) l=c;
						else r=c;
					}
					tot += r;
				}
				if( A[i]*A[i] < x ) tot--;
			}
			tot/=2;
			return tot<k;
		}();
		// value
		if(ok) lb = x;
		else ub = x;
	}

	cout << lb << endl;
	return 0;
}

Measured memory_bytes: 1920
n, *a = map(int, open(0).read().split())
ans = 0
mod = 10 ** 9 + 7
for k in range(61):
	m = 1 << k
	c = 0
	for x in a:
		if m & x:
			c += 1
	ans += (c) * (n - c) * m
	ans %= mod
print(ans)


Measured memory_bytes: 155916
#include <iostream>

using namespace std;

int main()
{
    int n;

    // 料理数
    cin >> n;

    // 動的配列
    int *a = new int[n + 1];
    int *b = new int[n + 1];
    int *c = new int[n];
    
    // 食事順番および食事の満足度
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) cin >> b[i];
    for(int i=1; i<=n - 1; i++) cin >> c[i];

    // ダミーデータ
    a[0] = -1;

    // 満足度
    unsigned int ans = 0;

    // 演算
    for(int i=1; i<=n; i++){
        if(a[i] - a[i-1] == 1) ans += c[a[i-1]];
        ans += b[i];
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll unsigned long long
#define ld long double
#define pi 3.14159
#define mx 9999999
using namespace std;
ll mark[mx];
map<ll,ll> m;
int main()
{
    ll x;
    cin>>x;
    x=x-1;
    cout<<((x)*(x+1))/2;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <cstdlib>  // abs() for integer

using namespace std;

int main()
{
	int N;
	int a[100001][3];
	int b[3];

	cin >> N;
	for(int i = 1; i <= N; i++){
		for(int j = 0; j < 3; j++){
			cin >> a[i][j];
		}
	}

	for(int i = 1; i <= N; i++){
		for(int j = 0; j < 3; j++){
			b[j] = a[i][j] - a[i-1][j];
			//cout << b[j];
		}
		if(abs(b[1]) + abs(b[2]) > b[0]){
			cout << "No" << endl;
		  	return 0;
		}

		if((abs(b[1])%2 + abs(b[2])%2)%2 != b[0]%2){
			cout << "No" << endl;
		  	return 0;
		}
	}

	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 1408
n = int(input())
ps = list(map(int, input().split()))

cnt = 0
for i in range(1, n-1):
    if ps[i - 1] > ps[i] >= ps[i + 1]:
        cnt += 1
    elif ps[i + 1] > ps[i] >= ps[i - 1]:
        cnt += 1

print(cnt)

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

int n, m;
int a[11];

int main() {
	scanf("%d%d", &n, &m);
	memset(a, -1, sizeof a);
	
	bool chk = true;
	for(int i=0;i<m;i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		if(a[x]<0) a[x]=y;
		else
		if(a[x]!=y) chk = false;
	}
	if(n>1&&a[1]==0) chk = false;
	
	if(!chk) puts("-1");
	else {
		for(int i=1;i<=n;i++)
			if(a[i]<0) a[i]=((i==1&&n>1)?1:0);
		for(int i=1;i<=n;i++)
			printf("%d", a[i]);
		puts("");
	}
	
	return 0;
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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; }



int n, a[202020];
i64 d[202020];
i64 point(int p, int l, int r){
	if(p > r || p < 0) return LINF;
	return abs((d[p]-d[l])-(d[r]-d[p]));
}
void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		d[i+1] = d[i]+a[i];
	}
	
	i64 ans = LINF;
	for(int i = 2; i < n-1; i++){
		i64 l1 = 0,l2 = 0, r1 = 0,r2 = 0;
		//l = d[i], r = d[n]-d[i]
		
		i64 mid = d[i]/2;
		int p = lower_bound(d+1,d+i,mid)-d;
		if(point(p,0,i) == min({point(p,0,i),point(p+1,0,i),point(p-1,0,i)})){
			l1 = d[p]; l2 = d[i]-d[p];
		}
		if(point(p+1,0,i) == min({point(p,0,i),point(p+1,0,i),point(p-1,0,i)})){
			l1 = d[p+1]; l2 = d[i]-d[p+1];
		}
		if(point(p-1,0,i) == min({point(p,0,i),point(p+1,0,i),point(p-1,0,i)})){
			l1 = d[p-1]; l2 = d[i]-d[p-1];
		}
		
		mid = (d[n]+d[i])/2;
		p = lower_bound(d+i+1,d+n,mid)-d;
		if(point(p,i,n) == min({point(p,i,n),point(p+1,i,n),point(p-1,i,n)})){
			r1 = d[p]-d[i]; r2 = d[n]-d[p];
		}
		if(point(p+1,i,n) == min({point(p,i,n),point(p+1,i,n),point(p-1,i,n)})){
			r1 = d[p+1]-d[i]; r2 = d[n]-d[p+1];
		}
		if(point(p-1,i,n) == min({point(p,i,n),point(p+1,i,n),point(p-1,i,n)})){
			r1 = d[p-1]-d[i]; r2 = d[n]-d[p-1];
		}
		
		//cout << l1 << " " << l2 << " " << r1 << " " << r2 << endl;
		chmin(ans, max({l1,l2,r1,r2})-min({l1,l2,r1,r2}));
	}
	cout << ans << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

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

    vector<int> E(N + 1);
    vector<int> W(N + 1);
    rep(i, N) {
        E[i + 1] = E[i];
        W[i + 1] = W[i];
        if (S[i] == 'E') {
            E[i + 1]++;
        } else {
            W[i + 1]++;
        }
    }

    int ans = N;
    for (int i = 0; i < N; i++) {
        chmin(ans, W[i] + E[N] - E[i + 1]);
    }

    cout << ans << endl;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
#define ll long long
#define WEIGHTSUM weight + (it -> first)
#define VALUESUM (it -> second) + value
using namespace std;
map <int, ll> maxValue;

int main() {
	ll n, w, weight, value;

	cin >> n >> w;
	for (int i = 1; i <= n; i++) {
		cin >> weight >> value;

		for (map <int, ll> :: reverse_iterator it = maxValue.rbegin(); it != maxValue.rend(); it++)
			if (WEIGHTSUM <= w)
				maxValue[WEIGHTSUM] = max(maxValue[WEIGHTSUM], VALUESUM);

		maxValue[weight] = max(maxValue[weight], value);
	}

	ll result = 0;
    for (pair <int, ll> value : maxValue)
    	result = max(result, value.second);
    cout << result;

	return 0;
}


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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;


int main() {
  string s,t ; 
  cin >> s >> t  ; 
  int ans = t.size() ;
  
  rep(i,s.size() -t.size()+1) {
    int now = t.size() ;
    rep(j,t.size()){
      if(s.at(i+j) == t.at(j)) now-- ;
    }
    ans = min(ans,now) ;
  }
  
  cout << ans <<endl ;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fastio() ios_base::sync_with_stdio(false);
#define rmod(x, y) ((((x)%(y))+(y))%(y))
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T, typename R = null_type, typename C = less<T>>
tree<T, R, C, rb_tree_tag, tree_order_statistics_node_update> ordered_set(){
	return tree<T, R, C, rb_tree_tag, tree_order_statistics_node_update>();
}

const int maxn = 3005;
bool vis[maxn][maxn][2];
int n;
ll a[maxn], dp[maxn][maxn][2], pre[maxn];

inline ll get(int l, int r){return pre[r]-pre[l-1];}

ll solve(int l, int r, bool taro){
	if (l == r) {
		if (taro) return a[l];
		return -a[l];
	}
	ll &ret = dp[l][r][taro];
	if(vis[l][r][taro]) return ret;
	if (taro) ret = max(a[l]+solve(l+1, r, 0), a[r]+solve(l, r-1, 0));
	else ret = min(solve(l+1, r, 1)-a[l], solve(l,r-1, 1)-a[r]);
	vis[l][r][taro] = 1;
	return ret;
}


int main(){
	
	scanf("%d", &n);
	for(int i = 1; i<=n; i++) scanf("%lld", &a[i]), pre[i] = a[i]+pre[i-1];
	printf("%lld\n", solve(1, n, 1));
	return 0;
}


Measured memory_bytes: 158848
""" AtCoder """

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

ans = [0 for _ in range(N)]

for i in range(M):
    ans[ab[i][0]-1] += 1
    ans[ab[i][1]-1] += 1

for i in range(N):
    print(ans[i])


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ull = uint64_t;
const ll INF = 9e18;

void print() { cout << endl; }
template <typename Head, typename... Tail>
void print(Head head, Tail... tail) {
    int size = sizeof...(Tail);
    cout << head;
    if (size > 0) {
        cout << " ";
    }
    print(tail...);
}

void print0() {}
template <typename Head, typename... Tail>
void print0(Head head, Tail... tail) {
    cout << head;
    print0(tail...);
}

vector<map<ll, ll>> prime_factors(ll n) {
    // エラトステネスの篩
    vector<ll> divprimes(n + 1, -1);
    vector<bool> isprime(n + 1, true);
    isprime[0] = false;
    isprime[1] = false;
    for (ll i = 2; i <= n; i++) {
        if (isprime[i]) {
            divprimes[i] = i;
            for (ll j = 2 * i; j <= n; j += i) {
                divprimes[j] = i;  // その数をふるい落とした素数を記録
                isprime[j] = false;
            }
        }
    }

    vector<map<ll, ll>> result(n + 1);
    for (ll i = 2; i <= n; i++) {
        ll p = divprimes[i];
        if (p != i) {
            for (auto pf : result[i / p]) {
                result[i].insert(pf);
            }
        }
        if (result[i].count(p)) {
            result[i][p]++;
        } else {
            result[i][p] = 1;
        }
    }
    return result;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    ll maxval = 1000000;
    auto pfs = prime_factors(maxval);

    // debug
    // auto pfss = prime_factors(100);
    // for (ll i = 2; i <= 100; i++) {
    //     print0(i, " ");
    //     for (auto p : pfss[i]) {
    //         print0(p.first, ":", p.second, " ");
    //     }
    //     print();
    // }

    vector<ll> usecount(maxval + 1, 0);
    for (ll i = 0; i < N; i++) {
        ll n = A[i];
        for (auto pf : pfs[n]) {
            usecount[pf.first]++;
        }
    }
    ll maxusecount = 0;
    for (auto u : usecount) {
        maxusecount = max(maxusecount, u);
    }
    if (maxusecount == N) {
        print("not coprime");
        return 0;
    } else if (maxusecount >= 2) {
        print("setwise coprime");
        return 0;
    } else {
        print("pairwise coprime");
        return 0;
    }
}


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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int x, t; cin >> x >> t;
  cout << max(0, x - t) << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	while(1){
		int m, f, r;
		cin >> m >> f >> r;
		if (m==-1 && f==-1 && r==-1) break;
		char grade;
		if (m==-1 || f==-1) grade='F';
		else if (m+f>=80) grade = 'A';
		else if (m+f>=65) grade = 'B';
		else if (m+f>=50) grade = 'C';
		else if (m+f>=30) grade = (r>=50 ? 'C' : 'D');
		else grade = 'F';
		cout << grade << endl;
	}
	
	return 0;
}



Measured memory_bytes: 3116
from collections import deque

a,b,c = map(int,input().split())
k = int(input())
tmp = 0
flag = 0

q = deque([[a,b,c,k]])

while len(q) != 0:
    tmp = q.popleft()
    if tmp[0] < tmp[1] and tmp[1] < tmp[2]:
        print('Yes')
        flag = 1
        break
    elif tmp[3] > 0:
        q.append([tmp[0],2*tmp[1],tmp[2],tmp[3]-1])
        q.append([tmp[0],tmp[1],2*tmp[2],tmp[3]-1])

if flag == 0:
    print('No')


Measured memory_bytes: 9456
import java.util.*
fun main(args: Array<String>){
	val cin = Scanner(System.`in`)
    val h = cin.nextInt()
    val w = cin.nextInt()

    val h_d = cin.nextInt()
    val w_d = cin.nextInt()

    println(h*w - h_d*w - w_d*h + h_d*w_d)
    
    
}

Measured memory_bytes: 31276
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int cnt=0;
	for(int i=1;i<n;i++){
		cnt+=n/i;
		if(n%i==0)cnt--;
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 3668
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	table := make([]int, 100)
	now := 0
	max := 0
	for i := range table {
		table[i] = 0
	}
	for scanner.Scan() {
		now, _ =strconv.Atoi(scanner.Text())
		table[now-1]++
		if table[now-1] > max {
			max = table[now-1]
		}
	}
	for i := 0; i < 100; i++ {
		if table[i] == max {
			fmt.Println(i+1)
		}
	}
}


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

int w, h;
string s[21];

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

char f[256] = {0};
bool ans = false;
bool memo[21][21][4][16];

void init(){
	f['>'] = 0;
	f['<'] = 1;
	f['v'] = 2;
	f['^'] = 3;
	for(int y=0 ; y < 21 ; y++ ){
		for(int x=0 ; x < 21 ; x++ ){
			for(int i=0 ; i < 4 ; i++ ){
				for(int m=0 ; m < 16 ; m++ ){
					memo[y][x][i][m] = false;
				}
			}
		}
	}
}

void solve(int x, int y, int dir, int memory){
	if( ans ) return;
	if( memo[y][x][dir][memory] ) return;
	memo[y][x][dir][memory] = true;
	
	if( s[y][x] == '<' || s[y][x] == '>' || s[y][x] == '^' || s[y][x] == 'v' ){
		dir = f[ s[y][x] ];
		int mx = (x + dx[dir] + w) % w ;
		int my = (y + dy[dir] + h) % h ;
		solve( mx , my , dir , memory );
	}else if( s[y][x] == '_' ){
		if( memory == 0 ){
			dir = f['>'];
			int mx = (x + dx[dir] + w) % w ;
			int my = (y + dy[dir] + h) % h ;
			solve( mx , my , dir , memory );
		}else{
			dir = f['<'];
			int mx = (x + dx[dir] + w) % w ;
			int my = (y + dy[dir] + h) % h ;
			solve( mx , my , dir , memory );
		}
	}else if( s[y][x] == '|' ){
		if( memory == 0 ){
			dir = f['v'];
			int mx = (x + dx[dir] + w) % w ;
			int my = (y + dy[dir] + h) % h ;
			solve( mx , my , dir , memory );
		}else{
			dir = f['^'];
			int mx = (x + dx[dir] + w) % w ;
			int my = (y + dy[dir] + h) % h ;
			solve( mx , my , dir , memory );
		}
	}else if( s[y][x] == '+' ){
		memory = (memory + 1) % 16;
		int mx = (x + dx[dir] + w) % w ;
		int my = (y + dy[dir] + h) % h ;
		solve( mx , my , dir , memory );
	}else if( s[y][x] == '-' ){
		memory = (memory + 15) % 16;
		int mx = (x + dx[dir] + w) % w ;
		int my = (y + dy[dir] + h) % h ;
		solve( mx , my , dir , memory );
	}else if( s[y][x] >= '0' && s[y][x] <= '9' ){
		memory = s[y][x] - '0';
		int mx = (x + dx[dir] + w) % w ;
		int my = (y + dy[dir] + h) % h ;
		solve( mx , my , dir , memory );
	}else if( s[y][x] == '.' ){
		int mx = (x + dx[dir] + w) % w ;
		int my = (y + dy[dir] + h) % h ;
		solve( mx , my , dir , memory );
	}else if( s[y][x] == '?' ){
		for(int i=0 ; i < 4 ; i++ ){
			int mx = (x + dx[i] + w) % w ;
			int my = (y + dy[i] + h) % h ;
			solve( mx , my , i , memory );
		}
	}else if( s[y][x] == '@' ){
		ans = true;
		return;
	}
}

int main(){
	init();
	
	cin >> h >> w;
	for(int y=0 ; y < h ; y++ ){
		cin >> s[y];
	}
	solve( 0 , 0 , 0 , 0 );
	if( ans )
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

Measured memory_bytes: 0
def main():
    K, X = map(int, input().split())
    if K == 1:
        print(X)
        return
    ans = []
    ans.append(X)
    l = X
    r = X
    for i in range(K - 1):
        l = l - 1
        r = r + 1
        ans.append(l)
        ans.append(r)
    ans.sort()
    a = ''
    for i in range(len(ans)):
        a = a + str(ans[i]) + ' '
    print(a)
main()  

Measured memory_bytes: 9108
from collections import defaultdict
import sys
buf = sys.stdin.buffer


def main():
    n, k = map(int, buf.readline().split())
    AB = map(int, buf.read().split())

    count = defaultdict(int)
    for a, b in zip(AB, AB):
        count[a] += b

    idx = 0
    for num in sorted(count.keys()):
        idx += count[num]
        if idx >= k:
            print(num)
            break


if __name__ == "__main__":
    main()


Measured memory_bytes: 28736