akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define mp make_pair
#define inf 1000000007
#define int long long
using namespace std;
signed main(){
	int n;
	string s;
	cin>>n>>s;
	int lef = 0,rig = n/2 + 1;
	while(rig-lef>1){
		int mid = (lef+rig)/2;
		map<string,int> lmope,rmope;
		vector<string> v;
		for(int i=0;i<n-mid+1;i++){
			string st = s.substr(i,mid);
			v.pb(st);
			if(lmope[st]==0)lmope[st]=i+1;
			if(rmope[st]<i+1)rmope[st]=i+1;
		}
		bool fl =false;
		for(int i=0;i<v.size();i++){
			if( rmope[v[i]]-lmope[v[i]] >= mid)fl=true;
		}
		if(fl){
			lef = mid;
		}
		else{
			rig =mid;
		}
	}
	cout<<lef<<endl;
	return 0;
}

Measured memory_bytes: 8728
h, w = map(int,input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
dp = [[0] * w for i in range(h)]
dp[0][0] = 1

def mod(x):
    return x%(10**9+7)

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        elif i == 0:
            if grid[i][j-1] == ".":
                dp[i][j] = dp[i][j-1]
        elif j == 0:
            if grid[i-1][j] == ".":
                dp[i][j] = dp[i-1][j]
        else:
            if grid[i-1][j] == "#" and grid[i][j-1] == "#":
                continue
            elif grid[i-1][j] == "#":
                dp[i][j] = dp[i][j-1]
            elif grid[i][j-1] == "#":
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = mod(dp[i-1][j] + dp[i][j-1])
                
print(dp[h-1][w-1])

Measured memory_bytes: 89456
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<bits/stdc++.h>
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i,a,b) for(register int i=a;i<=b;++i)
#define repd(i,a,b) for(register int i=a;i>=b;--i)
#define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define ce(i,r) i==r?'\n':' '
#define pb push_back 
#define all(x) x.begin(),x.end()
#define fi first
#define se second
//#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;

const int N = 1e6 + 10;
typedef long long ll;
ll x,k,d;

int main(){
	sl(x),sl(k),sl(d);
	ll t1 = abs(x / d);
	if(t1 >= k){
		cout<<abs(x) - k * d<<endl;
	}
	else{
		if(t1 % 2 == k % 2){
			cout<<abs(x) - t1 * d<<endl;
		}
		else{
			cout<<abs(abs(x) - (t1 + 1) * d)<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3652
import bisect
n = int(input())
a = list(map(int,input().split()))
a.sort()
ma = max(a)

b = bisect.bisect(a,ma//2)
koho = []
if b-1 >= 0:
    koho.append([abs(ma//2-a[b-1]),a[b-1]])
if b < n-1:
    koho.append([abs(ma//2-a[b]),a[b]])

if ma % 2 == 1:
    b2 = bisect.bisect(a,ma//2+1)
    if b2-1 >= 0:
        koho.append([abs(ma//2+1-a[b2-1]),a[b2-1]])
    if b2 < n-1:
        koho.append([abs(ma//2+1-a[b2]),a[b2]])

koho.sort()
print(ma,koho[0][1])

Measured memory_bytes: 14160
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<map>

using namespace std;

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

  vector<int> v(N+1, 0);
  vector<int> vv;

  for (int i=0; i<N; i++) {
    v[A[i]]++;
  }

  for (int i=0; i<=N; i++) {
    if (v[i] != 0) vv.push_back(v[i]);
  }

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

  sort(vv.begin(), vv.end());

  int res = 0;
  for (int i=0; i<vv.size()-K; i++) {
    res += vv[i];
  }

  cout << res << endl;

  
    /*
  vector<pair<int, int>> v;
  map<int, int> m;

  for (int i=0; i<N; i++) {
    if (m.count(A[i]) == 0) m[A[i]] = 0;
    m[A[i]]++;
  }

  for (pair<int, int> p: m) {
    v.push_back(p);
  }
  */
}


Measured memory_bytes: 2936
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 600000;
bool isPrime[MAX];
bool used[MAX];
int N;
int prime[MAX];

void era(){
    fill(isPrime, isPrime+MAX, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i=2;i<MAX;i++){
        if(!isPrime[i]) continue;
        int j = i+i;
        while(j < MAX){
            isPrime[j] = false;
            j += i;
        }
    }
    int i=0, j = 2;
    while(j < MAX){
        if(isPrime[j]){
            prime[i] = j;
            i++;
            j++;
        }else{
            j++;
        }
    }
}

void sum_rec(int sum, int num, vector<int> tmp){
    if(num == 0){
        for(auto v : tmp) cout << v << " ";
        cout << endl;
        cout << sum << endl;
        return;
    }
    for(int i=3;i<MAX;i++){
        if(!used[i] && isPrime[i]){
            used[i] = true;
            tmp.push_back(prime[i]);
            sum_rec(sum + prime[i], num-1, tmp);
            tmp.pop_back();
        }
    }
}

vector<int> A;
void print_sum(vector<int> comb, int n, int r, int dep, int init){
    if(dep == r){
        int sum = 0;
        for(int i=0;i<r;i++){
            sum += A[comb[i]];
            cout << A[comb[i]] << " ";
        }
        cout << "   : " << sum << "   " << (!isPrime[sum] ? "" : "NG" ) << endl;
        return;
    }

    for(int i=init;i<=n-r+dep;++i){
        comb.push_back(i);
        print_sum(comb, n, r, dep+1, i+1);
        comb.pop_back();
    }
}


int main(){
    era();
    cin >> N;
    for(int i=0;i<MAX;i++){
        if(prime[i] % 5 == 1) A.push_back(prime[i++]);
        else i++;
        if(A.size() == N) break;
    }
    for(auto a : A) cout << a << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <limits>
#include <cmath>
#include <iomanip>
#include <functional>
#include <random>
#include <set>
using namespace std;
using ll = long long;
ll BASE_NUM = 1000000007;

int main()
{
    // 整数の入力
    ll H,W,K;
    cin >> H >> W >> K;
    vector<string> S(H);
    for(int i = 0; i < H;i++){
      cin >> S[i];
    }
    ll min_lines = BASE_NUM;
    for (int bit = 0; bit < (1<<(H-1)); ++bit){
      // cout << bitset<10>(bit) << endl;
      map<ll,ll> group;
      ll current_group = 0;
      ll holizontal_lines = 0;
      ll vertical_lines = 0;
      for(int i = 0;i < H;i++){
        group[i] = current_group;
        if (bit & 1<<i){
          current_group = i + 1;
          holizontal_lines++;
        }
      }
      map<ll,ll> counts;
      int i = 0;
      int start_from = 0;
      while(i < W){
        if (counts.empty()){
          start_from = i;
        }
        for(int j = 0;j< H;j++){
          if(S[j][i] == '1'){
           counts[group[j]]++;
          }
        }
        bool not_over = true;
        for(auto p:counts){
          if(p.second > K){
            not_over = false;
            break;
          };
        }
        if(not_over){
          i++;
        }else if(start_from == i){
          vertical_lines = BASE_NUM;
          break;
        }else{
          counts.clear();
          vertical_lines++;
        }
      }
      // for(auto p:counts){
      //   cout << p.first << " " << p.second <<endl;
      // }
      min_lines =  min(min_lines,vertical_lines + holizontal_lines);
    }
    cout << min_lines << endl;
    return 0;
}


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

int main() {
	int m, k;
	scanf("%d%d", &m, &k);
	int mx=(1<<m)-1;
	if (k>mx || (m==1 && k==1)) {
		printf("-1\n");
		return 0;
	}
	else if (m==1 && k==0) {
		printf("0 0 1 1 \n");
		return 0;
	}
	int arr[1<<(m+1)];
	int cnt=0;
	for (int i=0; i<(1<<m)-1; i++) {
		if (cnt==k) cnt++;
		arr[i]=cnt;
		cnt++;
	}
	arr[(1<<m)-1]=k;
	cnt--;
	for (int i=(1<<m); i<(1<<(m+1))-1; i++) {
		if (cnt==k) cnt--;
		arr[i]=cnt;
		cnt--;
	}
	arr[(1<<(m+1))-1]=k;
	/*
	bool fail=false;
	for (int i=0; i<(1<<(m+1)); i++) {
		int x=arr[i];
		for (int j=i+1; j<(1<<(m+1)); j++) {
			x^=arr[j];
			if (arr[i]==arr[j]) {
				if (x!=k) fail=true;
				break;
			}
		}
		if (fail) break;
	}
	if (fail) printf("FAIL\n");*/
		
	for (int i=0; i<(1<<(m+1)); i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}


Measured memory_bytes: 2816
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね

//ここから編集する

vector<vector<int> > d;//頂点iからjまでの最短距離,間に編がない場合はINFが入る。
int V;//超点数

void washall() {
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

int main() {
    int N, M, R;
    cin >> N >> M >> R;
    V = N;
    d = vector<vector<int> >(N, vector<int>(N, INF));
    vector<int> r(R);
    REP(i, 0, R) {
        cin >> r[i];
        r[i]--;
    }
    sort(r.begin(),r.end());
    REP(i, 0, M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        d[a][b] = c;
        d[b][a] = c;
    }
    washall();
    int ans = INF;
    do {
        int sum_d = 0;
        REP(i, 0, r.size() - 1) {
            sum_d += d[r[i]][r[i + 1]];
        }
        ans = min(sum_d, ans);
    } while (next_permutation(r.begin(), r.end()));     // 次の順列を生成

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


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

const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
  long long int n, r;
  cin >> n;
  map<long long int, long long int> mp;
  r = 0;
  for (long long int i = 1; i <= n; i++) {
    long long int alt;
    cin >> alt;
    r += mp[i - alt];
    mp[i + alt]++;
  }
  cout << r << endl;
  return 0;
}

Measured memory_bytes: 26200
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include<iomanip>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define ffrvs(ii,nn,mm) for(int ii=nn;ii>=mm;ii--)
#define srt(vvv) sort(vvv.begin(),vvv.end())
#define srtrvs(vvv) reverse(vvv.begin(),vvv.end())
#define Graph vector<vector<int>>

i64 inf = 1000000007;
i64 giant = 4000000000000000037;

using namespace std;

i64 cup(i64 xxx, i64 yyy) {//切り上げ
	return (xxx + yyy - 1) / yyy;
}

//メモリ置き場
string s;

//inputします
void input() {
	cin >> s;
}

//ライブラリ置き場

//main
int main() {
	input();
	if (s[0] == s[1] && s[1] == s[2]) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define chmax(a, b) a = max(a, b);
#define chmin(a, b) a = min(a, b);
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
	int x, y, z, k;
	cin >> x >> y >> z >> k;
	vector<ll> a(x), b(y), c(z);
	rep(i, x) cin >> a[i];
	rep(i, y) cin >> b[i];
	rep(i, z) cin >> c[i];
	sort(rall(a));
	sort(rall(b));
	sort(rall(c));
	ll l = 0, r = 30000000010LL;
	int cnt_r = 0;
	while(r - l > 1) {
		ll m = (l + r) / 2;
		int cnt = 0; // count of comb s.t. ai+bj+c?>=m
		rep(i, x) rep(j, y) {
			int l = -1, r = z;
			while(r - l > 1) {
				int m2 = (l + r) / 2;
				(a[i]+b[j]+c[m2] >= m ? l : r) = m2;
			}
			cnt += r;
		}
		if (cnt >= k) {
		       l = m;
		} else {
			r = m;
			cnt_r = cnt;
		}
	}
	vector<ll> ans(k - cnt_r, l);
	rep(i, x) rep(j, y) rep(p, z) {
		if (a[i] + b[j] + c[p] <= l) break;
		ans.push_back(a[i]+b[j]+c[p]);
	}
	sort(rall(ans));
	rep(i, k) cout << ans[i] << endl;
}


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

int main() {
	int a, b, c;
	int d,e;
	cin >>a >>b >>c;
	d = a - b;
	e = c - d;
	if (e >=0 ) {
		cout << e << "\n";
	}else{
		cout << 0 << "\n";
	}
	return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int INF=1001001001;
typedef pair<int,int>P;
const int dx[]={-1,0,1,0,0};
const int dy[]={0,-1,0,1,0};
int H,W;
char fld[50][50];
int sy,sx,gy,gx;
int dist[50][50];
int ord[10],N;
bool ok(int y,int x){
    if(y<0||y>=H||x<0||x>=W)return false;
    return true;
}

void bfs(){
    for(int i=0;i<H;i++)for(int j=0;j<W;j++)dist[i][j]=INF;
    dist[sy][sx]=0;

    queue<P>que;que.push(P(sy,sx));

    while(que.size()){
        P p=que.front();que.pop();

        for(int i=0;i<4;i++){
            int ny=p.first+dy[i],nx=p.second+dx[i];
            if(!ok(ny,nx)||fld[ny][nx]=='#'||dist[ny][nx]!=INF)continue;
            dist[ny][nx]=dist[p.first][p.second]+1;
            que.push(P(ny,nx));
        }
    }
}

void solve(){
    for(int i=0;i<H;i++){
        cin>>fld[i];
        for(int j=0;j<W;j++){
            if(fld[i][j]=='A')sy=i,sx=j;
            if(fld[i][j]=='B')gy=i,gx=j;
        }
    }

    bfs();

    string str;cin>>str;
    N=str.size();
    for(int i=0;i<N;i++){
        switch(str[i]){
            case '5':ord[i]=4;break;
            case '8':ord[i]=1;break;
            case '4':ord[i]=0;break;
            case '2':ord[i]=3;break;
            case '6':ord[i]=2;break;
        }
    }

    for(int i=0;i<100000;i++){
        int ny=gy+dy[ord[i%N]],nx=gx+dx[ord[i%N]];
        if(ok(ny,nx)){
            gy=ny;gx=nx;
        }

        if(dist[gy][gx]<=i+1){
            cout<<i+1<<" "<<gy<<" "<<gx<<endl;
            return;
        }
    }

    cout<<"impossible"<<endl;
}

int main(){
    while(cin>>H>>W,H||W)solve();
    return 0;
}

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

MOD = 10 ** 9 + 7

def comb(n, r):
    ret = 1
    for i in range(r):
        ret *= n - i
        ret *= pow(i+1, MOD-2, MOD)
        ret %= MOD

    return ret % MOD
    

ans = pow(2, n, MOD) - 1 - comb(n, a) - comb(n, b)
ans %= MOD
print(ans)


Measured memory_bytes: 41068
/*

    author : s@if

*/

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

#define 		NIL 			-1
#define		 	fi	 		    first
#define 		sec 			second
#define 		MAX 			INT_MAX
#define			INF 			1e9
#define 		ll 			    long long
#define 		PI 			    acos(-1.0)
#define			MOD 			1000000007
#define 		PLL 			pair<ll,ll>
#define 		PII			    pair<int,int>
#define 		ull 			unsigned long long
#define 		For(i,a,b) 		for(int i=a;i<=(int)b;i++)
typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> new_data_set;

//*find_by_order(k)  gives the kth element;
//order_of_key(item)   gives the index(number of element strictly less than item) of item;


inline int in() {int x; scanf("%d", &x); return x; }
bool Check(int N , int pos)	{	return (bool) (N & (1<<pos));}
int Set(int N, int pos) {	return N = N | (1<<pos);}

int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};
int hr[]={-2,-2,-1,+1,+2,+2,-1,+1};
int hc[]={+1,-1,+2,+2,-1,+1,-2,-2};
int dx[]={+1,-1,+0,+0};
int dy[]={+0,+0,+1,-1};

const int MAXN = (int)2e5+9;


int main()
{
/*	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);  */

    int i,j,k,l,m,n,p,q,x,y,u,v,r,tc,t;

    cin>>n>>m;

    p = n/m; if(n%m) p++;

    cout<<p<<endl;

    return 0;
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main() {
  int i,j,n,m,sel,k;
  int **Adj;
  scanf("%d",&n);
  Adj = malloc(n*sizeof(int *));
  for(i=0;i<n;i++)
    {
      Adj[i] = malloc(n*sizeof(int));
    }
  for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
	{
	  Adj[i][j] = 0;
	}
    }
  for(j=0;j<n;j++)
    {
      scanf("%d%d",&sel,&m);
      for(i=0;i<m;i++)
	{
	  scanf("%d",&k);
	  Adj[sel-1][k-1]++;
	}
    }

   for(i=0;i<n;i++)
    {
      for(j=0;j<n-1;j++)
	{
	  printf("%d ",Adj[i][j]);
	}
      printf("%d\n",Adj[i][j]);
    }
  return 0;
}



Measured memory_bytes: 2112
from itertools import accumulate
from bisect import *
n, m, k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

acc = [0] + list(accumulate(a))
acc1 = list(accumulate(b))
ans = 0
for i in range(n + 1):
    cnt = i
    temp = acc[i]
    left = k - temp
    if left < 0:continue 
    
    ind = bisect_right(acc1, left)
    cnt += ind
    if ans < cnt:
        ans = cnt
print(ans)


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

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

const int maxn = 10001;

int h,w,a[maxn],p=1,n;
stack <int> v;
void input();
void solve();

int main(){
	input();
	solve();
	
	return 0;
}
void input(){
	cin>>h>>w>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
}
void solve(){
	for (int j=0;j<h;j++){
		if (j%2==0){
			for (int i=0;i<w;i++){
				if (a[p]>1){
					cout<<p<<" ";
					a[p]--;
				}
				else{
					cout<<p<<" ";
					a[p]--;
					p++;
				}
			}
		}
		else{
			for (int i=0;i<w;i++){
				if (a[p]>1){
					v.push(p);
					a[p]--;
				}
				else{
					v.push(p);
					a[p]--;
					p++;
				}
			}
			for (int i=0;i<w;i++){
				cout<<v.top()<<" ";
				v.pop();
			}
		}
		cout<<endl;
	}
}

Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 87;
const int M = N * 2;
int n,a[N],f[M];
void add(int i)
{
    for (; i < M; i += i & -i)
        ++f[i];
}
int qry(int i)
{
    int r=0;
    for (; i ; i ^= i & -i)
        r += f[i];
    return r;
}
bool ok(int k)
{
    memset(f,0,sizeof(f));
    int s = N;
    add(s);
    long long t = (n * (n + 1LL) / 2 + 1) / 2;
    for (int i = 1; i <= n; ++i) {
        s += a[i] >= k ? 1 : -1;
        t -= qry(s);
        add(s);
    }
    return t <= 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int lo = 1, hi = 1e9;
    while (lo <= hi) {
        int mi = (lo + hi) / 2;
        if (ok(mi))
            lo = mi + 1;
        else
            hi = mi - 1;
    }
    cout << hi << '\n';
}


Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = (1ll<<31)-1;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;
    cin >> n >> k;
    ll ans = 0;
    rep(i,k+1,n+1){
        ans += (n/i)*(i-k);
        if (n%i >= k){
            ans += n%i-k+1;
            if (k == 0) ans--;
        }
    }
    PRINT(ans);
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
counter=1
res=0
for i in range(len(A)-1):
    if (A[i+1]<A[i] and res>0) or (A[i+1]>A[i] and res<0):
        counter+=1
        res=0
    elif A[i+1]!=A[i]:
        res=A[i+1]-A[i]


print(counter)


Measured memory_bytes: 85308
from collections import Counter
from collections import deque
import math
import bisect
import sys
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))
 
def f(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return divisors
n=int(input())
l=f(n)
ans=10**10
for i in l:

    ans=min(ans,max(len(str(i)),len(str(n//i))))
print(ans)

Measured memory_bytes: 3828
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;

int main(){
  int x,ans,sum=0;
  cin >> x;
  for (int i=0;i<=x;i++){
    sum+=i;
    if(sum>=x){
      ans = i;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int k, a, b, check;
    scanf("%d%d%d", &k, &a, &b);
    if(a-b<k){
        for(int i=a; i<=b; i++){
            if(i%k==0){
                printf("OK\n");
                return 0;
            }
        }
        printf("NG\n");
    }
    else{
        printf("OK\n");
    }
    return 0;
}


Measured memory_bytes: 1664
N,M = map(int,input().split())
if N >= 2 and M >= 2:
    ans = (N - 2) * (M - 2)
elif N == 1 and M >= 2:
    ans = (M - 2)
elif N >= 2 and M == 1:
    ans = (N - 2)
else:
    ans = 1
print(ans)

Measured memory_bytes: 2940
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
    
    Scanner cin = new Scanner(System.in);
    
    int H = cin.nextInt();
    int W = cin.nextInt();
    cin.close();
    long result = 0L;    
    if(W==H){
        result = calcMin(H,W);
    }else{
        result = Math.min(calcMin(H,W),calcMin(W,H));
    }
    System.out.println(result);
    }
    
    public static long calcMin(int H,int W){
        long S1 = 0L;
        long S2 = 0L;
        long S3 = 0L;
        long S4 = 0L;
        long S5 = 0L;
        long Smin = Long.MAX_VALUE;
        long tmpS;
        for(long i=1;i<H;i++){
            S1 = i*W;
            S2 = (H-i)*(W/2);
            S3 = (H-i)*(W-(W/2));
            tmpS = Math.max(Math.max(S1,S2),S3) - Math.min(Math.min(S1,S2),S3); 
            if(tmpS<Smin){
                Smin = tmpS;
            }
            if(i<=H-2){
                S4 = W*((H-i)/2);
                S5 = W*(H-i-((H-i)/2));
                tmpS = Math.max(Math.max(S1,S4),S5) - Math.min(Math.min(S1,S4),S5);
                if(tmpS<Smin){
                    Smin = tmpS;
                }
            }
        }
        return Smin;
    }
}

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

using namespace std;

int main()
{
    int K, S, X, Y, Z, Sum = 0;
    cin >> K >> S;

    for (int i = 0; i <= K; i++)
    {

        for (int a = 0; a <= K; a++)
        {
            X = i;
            Y = a;
            Z = S - X - Y;

            if (Z <= K && 0 <= Z)
            {
                Sum++;
            }
        }
    }
    cout << Sum;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

int main() {
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    double distance = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    printf("%.5lf\n", distance);

    return 0;
}




Measured memory_bytes: 3204
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

n , q = map(int,input().split())
point = [0] * n
edge = [[] for i in range(n)]

for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

for _ in range(q):
    a , b = map(int,input().split())
    point[a-1] += b

def dfs(now, last=-1):
    for nxt in edge[now]:
        if nxt==last: continue
        point[nxt] += point[now]
        dfs(nxt, now)
dfs(0)
print(*point)

Measured memory_bytes: 268432
#include <iostream>
#include <list>
#include <vector>

using namespace std;
int main() {
  int n;
  cin >> n;
  vector<list<int>> s(n);
  int q, t, x;
  cin >> q;
  while (cin >> q >> t) {
    if (q == 0) {
      cin >> x;
      s[t].push_back(x);
    } else if (q == 1) {
      if (!s[t].empty()) {
        cout << s[t].front();
        for (auto it = ++s[t].begin(); it != s[t].end(); ++it)
          cout << " " << *it;
      }
      cout << endl;
    } else {
      cin >> x;
      s[x].splice(s[x].cend(), s[t]);
    }
  }
}


Measured memory_bytes: 18732
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<cstring>
using namespace std;

int main(){
	int i,j,N,ball;
    cin>>N;
    for(i=0;i<N;i++){
		int ri=0,le=0,flg=0;
		for(j=0;j<10;j++){
			cin>>ball;
			if(ri<ball){
				ri=ball;
			}else if(le<ball){
				le=ball;
			}else{
				flg=1;
			}
		}		
		if(flg==0){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
    }
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// -9.2e-18 <= long long <= 9.2e18
// 0 <= unsigned int <= 4.2e9
// 0 <= unsigned long long <= 18.4e18
// cout << fixed << setprecision(10);

int main() {
    int D, T, S;
    cin >> D >> T >> S;
    if (D <= (T * S))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


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

typedef long long  ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;

#define INPUT(arr,n) for(ll i = 0;i<n;i++) cin>>arr[i];
#define PRINT(arr,n) for(ll i = 0;i<=n;i++) printf("%lld ",arr[i]);printf("\n");
#define MEM(var,val) memset(var,(val),sizeof(var))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define pb push_back

const ll NMAX = 100000+7;
const ll MOD = 1000*1000*1000+7;
const ll INT_BITS = 32 ;
ll arr[NMAX];

inline ll add(ll a, ll b) {
  ll r = a + b;
  return (r >= MOD ? r - MOD : r);
}

inline ll sub(ll a, ll b) {
  ll r = a - b;
  return (r < 0 ? r + MOD : r);
}

inline ll mul(ll a, ll b) {
  ll r = a * b;
  return (r >= MOD ? r % MOD : r);
}
ll dp[NMAX];

ll N,K=2;
ll func(ll i,ll K){
  if(dp[i]!=-1)return dp[i];
  if(i>=N-1)
    return 0;
  ll res = 1e18;
  for(ll k = 1;k<=K;k++){
    if(i+k<=N-1)
      res = min(res,func(i+k,K)+ abs(arr[i]-arr[i+k]));
  }
  return dp[i] = res;
}

int main(int argc, char const *argv[])
{
	MEM(dp,-1);
  cin>>N;
  cin>>K;
	INPUT(arr,N);
  cout<<func(0,K)<<endl;
  // PRINT(dp,N);
	return 0;
}

Measured memory_bytes: 6528
#include<stdio.h>
int main(){
int H,W,a[300],b[300],i=0,N=0;
scanf("%d %d",&a[0],&b[0]);
while(a[i]!=0||b[i]!=0)
{
N++;
i++;
scanf("%d %d",&a[i],&b[i]);
}
for(i=0;i<=N-1;i++)
{
   for(W=1;W<=b[i];W++)
   {
      printf("#");
   }
   printf("\n");
   for(H=2;H<=a[i]-1;H++)
    {
      printf("#");
      for(W=2;W<=b[i]-1;W++)
      {
         printf(".");
      }
     printf("#\n");
    }
   for(W=1;W<=b[i];W++)
   {
      printf("#");
   }
printf("\n");
printf("\n");
}
return 0;
}


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

typedef long long ll;

using namespace std;

int main()
{
    ll n, d;
    cin >> n >> d;

    if ((n % (2*d + 1)) == 0)
        cout << n / (2*d + 1)  << endl;
    else
        cout << n / (2*d + 1)+1  << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>    
using namespace std;
#define ll long long 
#define pi pair<ll,ll>
#define pd pair<ld,ld>
#define pb push_back
#define inf 1e16
#define mod 998244353
#define en '\n'
#define ld long double
#define ff first
#define ss second
#define ull unsigned long long 
ll pw(ll b, ll r, ll md){
	ll ans = 1;
	while(r){
		if(r&1)ans = (ans*b)%md;
		b = (b*b)%md;
		r>>=1;
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string s;cin>>s;
	if(s[2]==s[3]&&s[4]==s[5])cout<<"Yes\n";
	else cout<<"No\n";
	return 0 ; 
}

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

#define REP(i, s, e) for (ll i = s; i < e; ++i)

using namespace std;
using ll = long long;
using ld = long double;

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

    int N;
    cin >> N;
    int result = 0;
    for (int i = 1; i <= N; i += 2)
    {
        int c = 0;
        for (int j = 1; j <= i; j++)
        {
            if (i % j == 0) ++c;
        }
        if (c == 8)++result;
    }

    cout << result << endl;

    return 0;
}


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

#define min(a, b) ((a>b)?(b):(a))

int qsort_compare_int(const void *a, const void *b)
{
    return *(int *) a - *(int *) b; //昇順
}

int main(int argc, char *argv[])
{
    int n, a, b;
    int p[100];
    int ans;
    int i;
    int a_n, b_n, c_n;

    scanf("%d %d %d", &n, &a, &b);

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

    //qsort(p, n, sizeof(int), qsort_compare_int);

    a_n = 0;
    b_n = 0;
    c_n = 0;
    for (i = 0; i < n; i++) {
        if (p[i] <= a) {
            a_n++;
        } else if (p[i] <= b) {
            b_n++;
        } else {
            c_n++;
        }
    }


    c_n = n - a_n - b_n;
    ans = min(a_n, b_n);
    ans = min(ans, c_n);

    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
K = int(input())
L = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(L[K-1])


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int main(){
  set<int> U;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++){
    int a;
    cin >> a;
    U.insert(a);
  }
  int m;
  cin >> m;
  for (int i = 0; i < m; i++){
    int b;
    cin >> b;
    U.erase(b);
  }
  for (auto itr = U.begin(); itr != U.end(); itr++){
    cout << *itr << endl;
  }
}


Measured memory_bytes: 12472
#include<iostream>
#include<string>
using namespace std;
typedef long long LL;
#define int LL
signed main() {
	int n;
	cin >> n;
	int ans = 1;
	for (int i = 1; i <= n; i++) {
		ans *= i;
		ans %= 1000000007;
	}
	cout << ans << endl;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> p(m), ac(n + 1), wa(n + 1);
  vector<string> s(m);
  rep(i, m) cin >> p[i] >> s[i];
  int nac = 0, np = 0;
  rep(i, m) {
    if (s[i] == "AC" && !ac[p[i]]) {
      ac[p[i]] = 1;
      nac++;
      np += wa[p[i]];
    } else {
      wa[p[i]]++;
    }
  }
  cout << nac << " " << np << endl;
  return 0;
}


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

int main(void) {
    string S;
    cin >> S;
    if (S[0]=='S') cout << "Cloudy" << endl;
    else if (S[0]=='C') cout << "Rainy" << endl;
    else cout << "Sunny" << endl; 


 
    return 0;
}

Measured memory_bytes: 256
#include <string.h>
#include <stdio.h>
int main(){
  int i,j,q,x,y;
  char str[1000],str2[10],w[1000],r;
  scanf("%s %d",str,&q);
  for(i=0;i<q;i++){
    scanf(" %s",str2);
    if(strcmp(str2,"replace")==0){
      scanf(" %d %d %s",&x,&y,w);
      for(j=x;j<=y;j++){
        str[j]=w[j-x];
      }
    }
    else if(strcmp(str2,"reverse")==0){
      scanf(" %d %d",&x,&y);
      while(x<y){
        r=str[x];
        str[x]=str[y];
        str[y]=r;
        x++;
        y--;
      }
    }
    else if(strcmp(str2,"print")==0){
      scanf(" %d %d",&x,&y);
        for(j=x;j<=y;j++){
          printf("%c",str[j]);
      }
      printf("\n");
    }
  }
  return 0;
}

Measured memory_bytes: 2596
import sys

l = []
for i in sys.stdin:
    l.append(i.split())

def bubble_sort(data):
    count = 0
    for i in range(0,len(data)):
        for j in range(len(data)-1,i,-1):
            if data[j] < data[j-1]:
                count += 1
                temp = data[j]
                data[j] = data[j-1]
                data[j-1] = temp
    for i in range(0,len(data)):
        print(data[i],end='')
        print(" ",end='') if i < len(data)-1 else print()
    print(count)

for i in range(0,len(l[1])):
    l[1][i] = int(l[1][i])

bubble_sort(l[1])


Measured memory_bytes: 5628
#include <iostream>
#include <algorithm>
#include <vector>

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

    std::vector<int> pts(3);
    for (auto& pt : pts) {
        std::cin >> pt;
    }

    std::vector<std::vector<int>> hands(k);
    for (int i = 0; i < n; ++i) {
        char c;
        std::cin >> c;
        for (int j = 0; j < 3; ++j) {
            if (c == "spr"[j]) {
                hands[i % k].push_back(j);
            }
        }
    }

    int ans = 0;
    for (auto& hand : hands) {
        std::vector<int> dp(3, 0), ndp(3);
        dp[hand[0]] = pts[hand[0]];
        hand.erase(hand.begin());

        for (auto h : hand) {
            std::fill(ndp.begin(), ndp.end(), 0);
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    if (i == j) continue;
                    ndp[j] = std::max(ndp[j], dp[i] + (h == j ? pts[j] : 0));
                }
            }
            std::swap(dp, ndp);
        }
        ans += *std::max_element(dp.begin(), dp.end());
    }

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


Measured memory_bytes: 5120
import std.stdio,std.string,std.conv,std.algorithm;

int ans[10];

void solve(int a[10],int n)
{
	int count = 0;
	foreach(i;0..a.length) count += a[i];

	if(count == 0)
	{
		ans[n] = 1;
		return;
	}

	foreach(i;1..10)
	{
		if(a[i] >= 3)
		{
			a[i] -= 3;
			solve(a,n);
			a[i] += 3;
		}
	}

	foreach(i;3..10)
	{
		if(a[i-2] && a[i-1] && a[i])
		{
			a[i-2]--; a[i-1]--; a[i]--;
			solve(a,n);
			a[i-2]++; a[i-1]++; a[i]++;
		}
	}
}

int main()
{
	string s;
	while((s = readln.chomp).length != 0)
	{
		foreach(i;0..10)
		{
			ans[i] = 0;
		}

		int a[10];
		foreach(i;0..s.length) a[s[i] - '0']++;

		foreach(i;1..10)
		{
			if(a[i] == 4)
			{
				continue;
			}
			else
			{
				a[i]++;
				foreach(j;1..10)
				{
					if(a[j] >= 2)
					{
						a[j] -= 2;
						solve(a,i);
						a[j] += 2;
					}
				}
				a[i]--;
			}
		}
		bool count_0 = true;
		int ans_max = 0;
		foreach(i;0..10)
		{
			if(ans[i])
			{
				if(ans[i])
				{
					count_0 = false;
					ans_max = max(ans_max,i);
				}
			}
		}

		if(count_0)
		{
			0.writeln;
		}
		else
		{
			bool flag = true;
			foreach(i;1..10)
			{
				if(ans[i] == 1)
				{
					if(i == ans_max)
					{
						i.writeln;
					}
					else
					{
						write(i," ");
					}
				}
			}
		}
	}
	return 0;
}

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

int main()
{
  int n;
  int node_nums[1000100] = {0};

  cin >> n;
  int value;
  int max_depth = 0;
  for (int i = 0; i < n; ++i)
  {
    cin >> value;
    if (i == 0 && value != 0)
    {
      cout << 0 << endl;
      return 0;
    }
    node_nums[value]++;
    if (value > max_depth)
    {
      max_depth = value;
    }
  }
  if (node_nums[0] != 1)
  {
    cout << 0 << endl;
    return 0;
  }

  unsigned long long mod = 998244353;
  unsigned long long result = 1;
  for (int i = 1; i <= max_depth; ++i)
  {
    for (int j = 0; j < node_nums[i]; ++j)
    {
      result *= node_nums[i - 1] % mod;
      result %= mod;
    }
  }

  cout << result % mod << endl;
  return 0;
}

Measured memory_bytes: 4096
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    bool b = true;
    int N; cin >> N;
    map<ll, int> A;
    repp(i,0,N) {
        ll a; cin >> a;
        A[a]++;
        b &= A[a] < 2;
    }
    if (b) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 12800
// abc137d.cpp : Summer Vacation
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n,m; cin>>n>>m;

	vector<vector<int>> w(m);
	while(n--){
		int a,b; cin>>a>>b;
		if(m<a) continue;
		w[m-a].push_back(b);
	}

	priority_queue<int> q;

	long long ans = 0;
	for(int i=m-1; i>=0; i--){
		for(int j=0; j<w[i].size(); j++) q.push(w[i][j]);
		if(!q.empty()){ ans += q.top(); q.pop(); }
	}
	cout<< ans <<endl;
}

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

int main() {
    int N, M;
    cin>>N>>M;
    //偶数2つ
    //奇数2つ
    int x = N * (N - 1) / 2;
    int y = M * (M - 1) / 2;
    cout << x + y << endl;
}

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

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

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

int x[100010], cnt[100010], cnt2[100010];
VI g[100010];
PII a[100010];
signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, n) {
    cin >> x[i];
    cnt[x[i]%m]++;
    g[x[i]%m].PB(x[i]);
  }
  REP(i, m) {
    if(g[i].size() == 0) continue;
    sort(ALL(g[i]));
    int c = 1;
    // for(int j: g[i]) cout << j << " "; cout << endl;
    FOR(j, 1, g[i].size()) {
      if(g[i][j] == g[i][j-1]) {
        c++;
      } else {
        a[i].first += c%2==1;
        a[i].second += c/2;
        c = 1;
      }
    }
    a[i].first += c%2==1;
    a[i].second += c/2;
  }
  // REP(i, m) cout << a[i].first << "," << a[i].second << " "; cout << endl;

  int ret = 0;
  REP(i, m/2+1) {
    if(i == 0 || i*2 == m) {
      ret += cnt[i]/2;
    } else {
      int tmp = min(cnt[i], cnt[m-i]);
      // cout << tmp << " ";
      ret += tmp;
      if(a[i].first >= tmp) ret += a[i].second;
      else ret += max(0LL, a[i].second - (tmp - a[i].first - 1)/2 - 1);
      if(a[m-i].first >= tmp) ret += a[m-i].second;
      else ret += max(0LL, a[m-i].second - (tmp - a[m-i].first - 1)/2 - 1);
    }
    // cout << i << " " << ret << endl;
  }
  cout << ret << endl;

  return 0;
}


Measured memory_bytes: 9600
dp={}
n=int(input())
nums=list(map(int,input().split()))
#print(dp)
#print(recursive(0,n-1))
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(i,n,1):
        dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
print(dp[0][n-1])



Measured memory_bytes: 135320
from collections import deque
n,m=map(int,input().split())
seen=[False]*n
num=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    num[a-1].append(b)
    num[b-1].append(a)
ans=0
for i in range(n):
    if seen[i]==False:
        queue=deque()
        queue.append(i)
        cnt=1
        yn=0
        while yn!=1:
            if len(queue)!=0:
                num01=queue.popleft()
            else:
                yn=1
            seen[num01]=True
            for j in range(len(num[num01])):
                num10=num[num01][j]-1
                if seen[num10]==False:
                    seen[num10]=True
                    cnt+=1
                    queue.append(num10)
        ans=max(ans,cnt)
print(ans)


Measured memory_bytes: 45948
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;

int main()
{
    ios_base::sync_with_stdio(0);
    ll n, d;
    cin >> n >> d;
    const ll N = n;
    const ll D = d;
    ll a[N][D];
    ll sum;

    for(ll i = 0; i < N; i++)
    {
        for(ll j = 0; j < D; j++)
        {
            cin >> a[i][j];
        }
    }
    ll cnt = 0;
    for(ll i = 0; i < N; i++)
    {
        for(ll j = i+1; j < N; j++)
        {
             sum = 0;
            for(ll k = 0; k < D; k++)
            {
                sum +=   ( a[i][k] - a[j][k] )  *   ( a[i][k] - a[j][k] ) ;
            }

            for(ll p = 0; p*p <= sum; p++)
            {
                if(p*p == sum)
                {
                    cnt++;
                }
            }




        }
    }
    cout << cnt;


}



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

using namespace std;

typedef long long ll;

constexpr ll mod = 1e9 + 7;
#define COMB_MAX (int)2e5

ll modfactorial(ll n)
{
    if (n <= 1)
    {
        return 1;
    }
    else
    {
        return (modfactorial(n - 1) * n) % mod;
    }
}

ll modpow(ll a, ll n)
{
    ll ret = 1;
    while (n > 0)
    {
        if ((n & 1) != 0)
        {
            ret = (ret * a) % mod;
        }
        a = (a * a) % mod;
        n = n >> 1;
    }
    return ret;
}
ll modcomb(ll n,ll k)
{
    ll ret=1;

    for(ll l=n;l >= n-k+1;l-=1)
    {
        ret = (ret *l)%mod;
    }
    ret = (ret*modpow(modfactorial(k),mod-2)) % mod;

    return ret;
}

int main(int argc, char const *argv[])
{
    ll n,a,b;
    cin >> n >> a >> b;

    ll m= (modpow(2,n) -1)%mod;
    m = (m-modcomb(n,a))%mod;
    m = (m-modcomb(n,b))%mod;
    if(m < 0)
    {
        m += mod;
    }
    cout << m<<endl;
    return 0;
}

Measured memory_bytes: 3328
main = do
  s <- getContents
  let t =  map aux $ takeWhile (/=[0,0]) $ map (map (read::String->Int) .  words) . lines $ s
  mapM_ putStrLn t

aux :: [Int] ->String  
aux f = concat $ map ((++"\n").take w) $ take h $ v
  --map (take w) $ (take h) $  v
    where
      [h,w]=f
      n = 300
      m = n `div` 2
      s = (concat (replicate m "#."))
      t = (concat (replicate m ".#"))
      u = [s, t]
      v = (concat . replicate m) u

Measured memory_bytes: 4944
visited = {0: -1}
height = 0
pools = []
for i, c in enumerate(input()):
    if c == '\\':
        height -= 1
    elif c == '/':
        height += 1
        if height in visited:
            width = i - visited[height]
            sm = 0
            while pools and pools[-1][0] > visited[height]:
                x, l = pools.pop()
                sm += l
            pools.append((i, sm + width - 1))
    visited[height] = i

print(sum(l for x, l in pools))
if pools:
    print(len(pools), ' '.join(str(l) for x, l in pools))
else:
    print(0)

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

bool budget[1000001], prime[1000001];

void eratosthenes() {
    fill(prime, prime+1000001, true);
    prime[0] = prime[1] = false;
    for (int i = 3; i <= 1000; i++) {
        if (prime[i]) {
            for (int d = i * 2, j = i + d; j <= 1000000; j += d) {
                prime[j] = false;
            }
        }
    }
}

int main() {
    int n, x, price[30], i, j;

    eratosthenes();

    while ((cin >> n >> x) && n) {
        for (i = 0; i < n; i++) {
            cin >> price[i];
        }
        // sort(price, price+n);

        fill(budget, budget+x+1, false);
        budget[0] = true;
        for (i = 0; i <= x; i++) {
            if (budget[i]) {
                for (j = 0; j < n; j++) {
                    if (i + price[j] <= x) {
                        budget[i + price[j]] = true;
                    }
                }
            }
        }

        for (i = x - 1 + (x&1); i > 0; i -= 2) {
            if (prime[i] && budget[i]) break;
        }

        if (i > 0) {
            cout << i;
        }
        else {
            cout << "NA";
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3108
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	ll n,i,m,ans=0ll;
	std::cin >> n;
	for(i=1ll; i<=n; ++i){
		m = n/i;
		ans += i*(m*(m+1)/2);
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 3640
My_s=[]
My_h=[]
My_c=[]
My_d=[]
s=[]
h=[]
c=[]
d=[]
for i in range(int(input())):
    x=input().split()
    if x[0]=='S':
        My_s.append(int(x[1]))
    elif x[0]=='H':
        My_h.append(int(x[1]))
    elif x[0]=='C':
        My_c.append(int(x[1]))
    elif x[0]=='D':
        My_d.append(int(x[1]))

for i in range(1,14):
    if i not in My_s:
        s.append(str(i))
    if i not in My_h:
        h.append(str(i))
    if i not in My_c:
        c.append(str(i))
    if i not in My_d:
        d.append(str(i))
for w in s:
    print('S '+w)
for w in h:
    print('H '+w)
for w in c:
    print('C '+w)
for w in d:
    print('D '+w)


Measured memory_bytes: 5608