akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
 
using namespace std;
 
const int inf = 1e9;
 
int n,m,g[705][705],col[705],vis[705],num[705][705],bk,f[705][705];
 
void dfs(int x){
	vis[x] = 1;++ num[col[x]][bk];
	for(int i=1;i<=n;i++)
		if(i!=x && !g[x][i]){
			if(!vis[i])col[i] = col[x] ^ 1, dfs(i);
			else if(col[i] == col[x]){puts("-1");exit(0);}
		}
}
int c(int x,int y){return (x*(x-1) + y*(y-1)) / 2;}
 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		g[x][y] = g[y][x] = 1;
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])++bk, dfs(i);
	f[0][0] = 1;
	for(int i=0;i<bk;i++)for(int j=0;j<=n;j++)
		f[i+1][j+num[0][i+1]] |= f[i][j],
		f[i+1][j+num[1][i+1]] |= f[i][j];
	int ans = inf;
	for(int i=0;i<=n;i++)if(f[bk][i])ans = min(ans,c(i,n-i));
	printf("%d\n",ans);
 
	return 0;
}

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

using namespace std;

const int N = 1e6 + 7 , mod = 1e9+7;

long long  n , m;
long long ans ; 

long long up(long long x){
    return x * (x+1) /2 ; 
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("in.in" , "r" , stdin) ;
    cin>>n>>m ; 
    for(int i = m ;i<=n+1; i++){
        long long L = up(i-1) ; 
        long long R = up(n) - up(n-i) ;
        long long add = (R-L+1)%mod ;
        ans = (ans + add) %mod ; 
    }
    cout<<ans ; 
    return 0;
}

Measured memory_bytes: 3668
n = int(input())
n = -n

if n == 0:
    print(0)
    exit()
t = []
while n != 0:
    s = n%-2
    if s == 0:
        t.append(0)
    else:
        t.append(1)
    n //= -2

t = t[::-1]
for i in t:
    print(i, end='')

Measured memory_bytes: 3060
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <deque>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

using namespace std;

// #define int long long

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

signed main(void)
{
  string s;
  cin >> s;
  if (s == "Sunny")
    cout << "Cloudy";
  else if (s == "Rainy")
    cout << "Sunny";
  else if (s == "Cloudy")
    cout << "Rainy";
  cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VP = vector<P>;
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; }

int main(){
    string s;
    cin >> s;
    auto iter = s.end() - 1;
    if (*iter == 's'){
        s += "es";
    }else{
        s += "s";
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
    #define rep(i,n) for(int i = 0; i < (n); i++)
     
    using namespace std;  
    
    int main() {
    while(true){
     int h,w;
     cin >> h >> w;
     if(h!=0 || w!=0){
     rep(i,h){
     	rep(j,w){
     	if(i%2==0){
     		if(j%2==0)cout <<  '#';
     		else	cout << '.';
     	} else{
     	    if(j%2==0)cout <<  '.';
     		else	cout << '#';
     	}
     	
     	}
     	cout << '\n';
     }
     cout << '\n';
     }else {
     return 0;
     }
     }
     return 0;
    }


Measured memory_bytes: 3092
#include<iostream>

int main(){
    int sum = 0;
    for(int i = 0; i < 3; i++){
        int tmp;
        std::cin >> tmp;
        sum += tmp;
    }
    if(sum >= 22) std::cout << "bust" << std::endl;
    else std::cout << "win" << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
 int a,b,c,d = 0;
 cin >> a >> b;
 while(!cin.eof()){
  c = a + b;
   for(;c != 0;++d){  
   c /= 10;
   }  
  cout << d << endl; 
  d = 0;
  cin >> a >> b;
  }
 return 0;
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';
ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
void setIO() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
using namespace std;
const int N = 3e5;

int n, Q;
struct Edge {
	int u, v, nxt;
}e[N * 2];
int head[N], en;
void addl(int x, int y) {
	e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int L[N], R[N], tot;
void dfs(int x,  int F) {
	L[x] = ++tot;
//	printf("x=%d\n", x);
	for(int i = head[x]; i;i = e[i].nxt) {
		int y = e[i].v;
		if(y == F) continue;
		dfs(y, x);
	}
	R[x] = tot;
}
ll c[N];
void add(int x, int v) {
	for(; x <= n; x += x & -x)
		c[x] += v;
}
ll query(int x) {
	ll res = 0;
	for(; x; x -= x & -x)
		res += c[x];
	return res;
}
int main() {
	n = read(), Q = read();
	for(int i = 1; i < n; ++i) {
		int x = read(), y = read();
		addl(x, y);
		addl(y, x);
	}
	dfs(1, 0);
	for(int i = 1; i <= Q; ++i) {
		int x = read(), y = read();
		add(L[x], y);
		add(R[x] + 1, -y);
	}
	for(int i = 1; i <= n; ++i)
		printf("%lld ", query(L[i]));
	puts("");
	return 0;
}

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


int main()
{
    int n;
    cin>>n;
    int a[n];
    int count=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++){
       if(a[i]==a[i+1]){
        a[i]=a[i+1]=0;
       }
    }
    for(int i=0;i<n;i++){
        if(a[i]!=0){
            count++;
        }
    }
    cout<<count;


}


Measured memory_bytes: 768
import collections

N = int(input())
A = sorted(list(map(int, input().split())))

dic = collections.Counter(A)
tmp = [0 for _ in range(A[-1]+1)]


for X in dic.keys():
    tmp[X] = dic[X]

ans = 0
for i in range(len(tmp)):
    ans = max(ans,sum(tmp[i:i+3]))

print(ans)


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

using namespace std;

int main(){
    int n;
    vector<pair<int,int> > v; //<B,A>
    int a,b;
    cin >> n;
    int dp[n+1][n+1];
    fill((int *)dp, (int *)dp+(n+1)*(n+1), 1 << 29);
    for(int i=0;i<n;i++){
        cin >> a >> b;
        v.push_back(make_pair(b,a));
    }
    dp[0][0] = 0;
    sort(v.begin(), v.end());
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(dp[i][j] + v[i].second <= v[i].first){
                dp[i+1][j+1] = min(dp[i][j+1], dp[i][j] + v[i].second);
            }
            dp[i+1][j] = min(dp[i][j],dp[i+1][j]);
        }
    }
    int ret;
    for(int i=0;i<=n;i++){
        if(dp[n][i] != 1<<29){
            ret = i;
        }
    }
    cout << ret << endl;
}

Measured memory_bytes: 0
<?php 
  fscanf(STDIN, "%d", $n);
  $arr = explode(" ", trim(fgets(STDIN)));

  $count = 0;
  for($i = 1; $i <= $n; $i++) {
    if($i != $arr[$i-1]) {
      $count++;
    }
  }

  if($count === 0 or $count === 2) {
    echo "YES";
  } else {
    echo "NO";
  }

Measured memory_bytes: 3576
/*
Author : N_o_o_B
Created : December 04 2019 01:08:36 
*/
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
#define TRACE
#ifdef TRACE
#define trace(...) { cerr<<"[ "; __trace__(#__VA_ARGS__, __VA_ARGS__);}
#undef endl
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const pair<Arg1,Arg2> &x) {
    return out<<"("<<x.first<<","<<x.second<<")";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const vector<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const set<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const map<Arg1,Arg2> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
void __trace__(const string name, Arg1&& arg1){
    cerr << name << " : " << arg1 << " ] " << endl;
}
 
template <typename Arg1, typename... Args>
void __trace__(const string names, Arg1&& arg1, Args&&... args){
    const string name = names.substr(0,names.find(','));
    cerr<<name<<" : "<<arg1<<" | ";
    __trace__(names.substr(1+(int)name.size()), args...);
}
#else
    #define trace(args...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vll;
typedef vector<vl> vvl;
//typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define fori(i,n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define ford(i,n)  for(int i=n-1;i>=0;i--)
#define trav(x,a) for(auto& x:a)
#define all(x) x.begin(),x.end()
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define fi first
#define se second
clock_t time_p=clock();
void time_taken()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
//const ll mod=998244353;
const ll mod=1e9+7;
const ll INF=1e18;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cout.precision(12);cout << fixed;
    string s;
    cin >> s;
    int n = sz(s);
    string ans;
    ans.resize(n);
    int i=0;
    trav(c,s){
        if(c=='0') ans[i++]='0';
        else if(c=='1') ans[i++]='1';
        else i=max(i-1,0);
    }
    fori(j,i){
        cout << ans[j];
    }
    cout << endl;


    time_taken();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
float PHI = 1.6180339;
//const float  PI_F=3.14159265358979f;
#define MAX 100000 
#define endl "\n"    
//typedef long long float;
#define int long long
//#define float unsigned long long

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin>>n;
    int arr[n+10];
    for(int i=0;i<n;i++)
    cin>>arr[i];
    int sum=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            int x=arr[i]*arr[j];
            sum+=x;
        }
    }
    cout<<sum<<endl;


}

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

//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;

#define ll  long long  int
#define ld   long double
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define pi 3.14159265358979
//#define goodset tree<pa, null_type, less<pa>, rb_tree_tag, tree_order_statistics_node_update>
//#define FRE freopen("acm.in","r",stdin); freopen("acm.out","w",stdout);

const ll mod = 1e9+7 ;
const ll N = 1e5+5;


int main()
{
    FAST
    ll i,j,k,tc;
    //cin>>tc;
    tc=1;
    while(tc--)
    {
        ll n;
        cin>>n;
        ll ans=0;
        for(i=1; i<=n-1; i++)
        {
            ll cnt=(n-1)/i;
            ans+=cnt;
        }
        cout<<ans<<"\n";
    }

    return 0;
}


Measured memory_bytes: 3648
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

array<vector<pair<int,int>>, 100000> to;
ll tod[100000];

int main() 
{
	int V, E, r;
	scanf("%d %d %d", &V, &E, &r);

	for (int i = 0; i < V; i++)
	{
		tod[i] = 200000000000;
	}

	for (int i = 0; i < E; i++)
	{
		int s, t, d;
		scanf("%d %d %d", &s, &t, &d);

		to[s].push_back(pair<int,int>(t, d));
	}

	priority_queue<pli, vector<pli>, greater<pli>> pq;
	pq.push(pli(0, r));
	tod[r] = 0;

	while (!pq.empty())
	{
		pli t = pq.top();
		pq.pop();

		if (tod[t.second] < t.first)
		{
			continue;
		}

		for (int i = 0; i != to[t.second].size(); i++)
		{
			if ((to[t.second][i].second + t.first) < tod[to[t.second][i].first])
			{
				tod[to[t.second][i].first] = (to[t.second][i].second + t.first);
				pq.push(pli(tod[to[t.second][i].first], to[t.second][i].first));
			}
		}
	}

	for (int i = 0; i < V; i++)
	{
		printf(tod[i] == 200000000000 ? "INF\n" : "%lld\n", tod[i]);
	}

	return 0;
}


Measured memory_bytes: 14344
#include<iostream>
using namespace std;
int main()
{
	int A, B, C, D, L, R;
	cin >> A >> B >> C >> D;
	L = A + B;
	R = C + D;
	if(L > R)
	{
		cout << "Left" << endl;
	}
	else if(R > L)
	{
		cout << "Right" << endl;
	}
	else
	{
		cout << "Balanced" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

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

int main() {

    int N;
    cin >> N;
    vector<int> A(N);
    rep(i,N) cin >> A[i];
    
    vector<P> p(N);
    rep(i,N) {
        p[i].first = A[i];
        p[i].second = i + 1;
    }

    sort(p.begin(), p.end(), greater<P>());

    set<int> S;
    S.insert(-1);
    S.insert(0);
    S.insert(N + 1);
    S.insert(N + 2);

    ll ans = 0;

    rep(i,N) {
        P q = p[i];
        S.insert(q.second);
        int w, x, y, z;
        decltype(S)::iterator it = S.lower_bound(q.second);
        y = *(++it);
        z = *(++it);
        decltype(S)::iterator it_low = S.lower_bound(q.second);
        x = *(--it_low);
        w = *(--it_low);
        if (w <= 0) w = 0;
        if (x <= 0) x = 0;
        if (y >= N + 1) y = N + 1;
        if (z >= N + 1) z = N + 1;
        ll count = 0;
        count += (x - w) * (y - q.second);
        count += (q.second - x) * (z - y);
        count *= q.first;
        ans += count;
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 9072
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1000000000
#define  pow(x) pow(10,(x)) 
typedef long long int LL;

int main(){
    int N,W; cin >> N;
    vector<int> We(N,0);
    vector<int> sum(N,0);
    rep(i,N){
        cin >> We[i];
        if(i == 0){
            sum[i] = We[i];
        }
        else{
            sum[i] = sum[i-1] + We[i];
        }
    }
    int temp;
    rep(j,N){
        if(j == 0){
            temp = abs(sum[N-1]-2*sum[j]);
        }
        else{
            temp = min(temp,abs(sum[N-1]-2*sum[j]));
        }
    }
    cout << temp << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000


int main(){
  unsigned short A[MAX],B[MAX];
  int C[VMAX+1];
  int n, i, j;
  unsigned short k;

  scanf("%d", &n);
  
 
  for(i=1; i<=n; i++){
    scanf("%hd",&A[i]);
    if(k < A[i]) k = A[i];
  }
  k++;
  for(i=0; i<=k; i++){
    C[i] = 0;
  }

  for(j=1; j<=n; j++){
    C[A[j]]++;
  }

  for(i=1; i<=k; i++){
    C[i] = C[i] + C[i-1];
  }

  for(j=n; j>=1; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
  
  for(i=1; i<=n; i++){
    printf("%d",B[i]);
    if(i == n) break;
    printf(" ");
  }
  printf("\n");
 
  return 0;
  
}



Measured memory_bytes: 9548
def trim(N):
    num=[]
    for x in range(8):
        for y in range(8):
            if N[y][x]=="1":
                if not num:
                    refer=(x,y)
                num.append((x,y))
    num=[(x-refer[0],y-refer[1]) for x,y in num]
    return num
def points(point):
    if point==[(0,0),(0,1),(1,0),(1,1)]:print("A")
    if point==[(0,0),(0,1),(0,2),(0,3)]:print("B")
    if point==[(0,0),(1,0),(2,0),(3,0)]:print("C")
    if point==[(0,0),(0,1),(1,-1),(1,0)]:print("D")
    if point==[(0,0),(1,0),(1,1),(2,1)]:print("E")
    if point==[(0,0),(0,1),(1,1),(1,2)]:print("F")
    if point==[(0,0),(1,-1),(1,0),(2,-1)]:print("G")
while True:
    N=[input() for _ in range(8)]
    points(trim(N))
    try:
        input()
    except:break



Measured memory_bytes: 5584
var
 n,m,j,i,d,x,y:longint;
begin
 readln(n,m,d);
 for i:=1 to n do
  begin
   for j:=1 to m do
    begin
     x:=(i+j+m-2) div d mod 2;
     y:=(i-j+m) div d mod 2;
     case 2*x+y of
      0:write('R');
      1:write('G');
      2:write('B');
      3:write('Y');
     end;
    end;
   writeln;
  end;  
end.

Measured memory_bytes: 384
/*  -*- coding: utf-8 -*-
 *
 * b.cc: B - YYMM or MMYY
 */

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

/* constant */

/* typedef */

/* global variables */

/* subroutines */

inline bool month(int d) { return d >= 1 && d <= 12; }

/* main */

int main() {
  int s;
  scanf("%d", &s);

  int d0 = s / 100, d1 = s % 100;

  if (month(d0) && month(d1)) puts("AMBIGUOUS");
  else if (month(d0)) puts("MMYY");
  else if (month(d1)) puts("YYMM");
  else puts("NA");
  return 0;
}


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

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    string ans = "No";
    rep(i, n+1) {
        rep(j, m+1) {
            if(i*(m-j)+j*(n-i)==k) {
                ans = "Yes";
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


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

//SUN, MON, TUE, WED, THU, FRI, or SAT
int main() {
    int n;
    cin>>n;
    getchar();
    int c;
    c=getchar();
    while(c>20){
        c+=n;
        if(c>90){
            c-=26;
        }
        printf("%c",c);
        
        c=getchar();
    }
}

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


int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
int k(int a,int b){
int s=1;
for(int l=1;;l++){
	s=s*a%b;
	if(s==1)return l;
}
}
signed main(){
int a,b,c,d,e,f;
while(cin>>a>>b>>c>>d>>e>>f,a||b||c||d||e||f){
	a=k(a,b);b=k(c,d);c=k(e,f);
	a=a*b/gcd(a,b);
	a=a*c/gcd(a,c);
	printf("%lld\n",a);
}
}

Measured memory_bytes: 3188
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <fstream>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int,int> PI;
typedef vector<PI> VPI;
typedef unsigned long long ull;
typedef long long ll;

#define FOR(i, n) for(int i=0;i<(n);++i)
#define REP(i,s,n) for(int i=s;i<=n;++i)
#define SZ(x) ((int)(x).size())
#define LOOP(i,x) FOR(i,SZ(x))
#define IT(it,x) for(typeof((x).begin()) it = (x).begin();it!=(x).end();++it)
#define ALL(x) (x).begin(), (x).end()
#define ST first
#define ND second
#define MP make_pair
#define PB push_back
#define gc getchar

const int INF = 1e9 + 5;
const int MAXN = 1e3 + 5;
const int MOD = 1e9 + 7;

string grid[MAXN];
int ways[MAXN][MAXN];
bool visited[MAXN][MAXN];

void add_self(int &a, int b) {
	a = a + b;
	if (a >= MOD) {
		a -= MOD;
	}
}

int dfs(int x, int y) {
	if (x < 0 || y < 0 || grid[x][y] == '#') return 0;
	if (x == 0 && y == 0) return 1;
	if (visited[x][y]) return ways[x][y];
	visited[x][y] = true;

	add_self(ways[x][y], dfs(x - 1, y) + dfs(x, y - 1));

	return ways[x][y];
}

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

	int rows, cols;
	cin >> rows >> cols;
	for (int i = 0; i < rows; i++) cin >> grid[i];
	dfs(rows, cols);
	cout << ways[rows - 1][cols - 1] << endl;

	return 0;
}

Measured memory_bytes: 6272
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
struct Node;
vector<Node> V;
vector<int> ans;
vector<int> init;
vector<int> init2;
vector<int> init3;
vector<int> dp;
struct Node {
  int idx;
  int a;
  vector<int> nbr;
  bool vst = false;
  void dfs() {
    vst = true;
    if(dp.size() == 0 || a > dp[dp.size()-1]) {
        dp.push_back(a);
        init.push_back(1);
    } else {
        int l = 0, r = dp.size() - 1;
        while (r - l >= 0) {
            int m = (l + r) / 2;
            if (a <= dp[m]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        init.push_back(0);
        init2.push_back(dp[l]);
        init3.push_back(l);
        dp[l] = a;
        
    }
    ans[idx] = dp.size();
    for(int x : nbr) {
      if(!V[x].vst) {
        V[x].dfs();
      }
    }
    if(init.size() > 0 && init[init.size()-1] == 0) {
        dp[init3[init3.size()-1]] = init2[init2.size()-1];
        init.pop_back();
        init2.pop_back();
        init3.pop_back();
    } else if(init.size() > 0) {
        dp.pop_back();
        init.pop_back();
    }
  };
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    REP(i, N) {
        V.emplace_back();
        V[i].idx = i;
        int a;
        cin >> a;
        V[i].a = a;
    }
    REP(i, N-1) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        V[u].nbr.push_back(v);
        V[v].nbr.push_back(u);
    }
    ans = vector<int>(N, 0);
    V[0].dfs();
    REP(i, N) cout << ans[i] << "\n";
}

Measured memory_bytes: 30156
S = input()
Odd = ["R", "U", "D"]
Even = ["L", "U", "D"]
f = 0
for index, i in enumerate(S):
    if index % 2 == 0:
        if i == "R" or i == "U" or i == "D":
            pass
        else:
            f = 1
            break
    else:
        if i == "L" or i == "U" or i == "D":
            pass
        else:
            f = 1
            break

if f == 1:
    print("No")

else:
    print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1005,mod=1e9+7;
int n,m;
LL k;
char s[N][N];
int Pow(int x,LL y){
	int ans=1;
	for (;y;y>>=1,x=1LL*x*x%mod)
		if (y&1LL)
			ans=1LL*ans*x%mod;
	return ans;
}
int f1=0,f2=0;
int check(){
	for (int i=1;i<=n;i++)
		if (s[i][1]=='#'&&s[i][m]=='#')
			f1++;
	for (int i=1;i<=m;i++)
		if (s[1][i]=='#'&&s[n][i]=='#')
			f2++;
	return (bool)f1+(bool)f2;
}
int cnts(){
	int cnt=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (s[i][j]=='#')
				cnt++;
	return cnt;
}
struct Mat{
	int v[2][2];
	Mat(){}
	Mat(int x){
		memset(v,0,sizeof v);
		for (int i=0;i<2;i++)
			v[i][i]=x;
	}
	void set(int c0,int c1,int c3){
		v[0][0]=c3	,v[0][1]=mod-c1	;
		v[1][0]=0	,v[1][1]=c0		;
	}
}M;
Mat operator * (Mat A,Mat B){
	Mat C(0);
	for (int i=0;i<2;i++)
		for (int j=0;j<2;j++)
			for (int k=0;k<2;k++)
				C.v[i][j]=(1LL*A.v[i][k]*B.v[k][j]+C.v[i][j])%mod;
	return C;
}
Mat Pow(Mat x,LL y){
	Mat ans(1);
	for (;y;y>>=1,x=x*x)
		if (y&1LL)
			ans=ans*x;
	return ans;
}
int main(){
	scanf("%d%d%lld",&n,&m,&k);
	if (k==0)
		return puts("1"),0;
	for (int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	int v=check(),c0=cnts();
	if (v==0)
		return printf("%d\n",Pow(c0,k-1)),0;
	if (v==2)
		return puts("1"),0;
	int c1=0,c2=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			if (j<m&&s[i][j]=='#'&&s[i][j+1]=='#')
				c1++;
			if (i<n&&s[i][j]=='#'&&s[i+1][j]=='#')
				c2++;
		}
	if (f2)
		swap(c1,c2),swap(f1,f2);
	M.set(c0,c1,f1);
	M=Pow(M,k-1);
	printf("%d",(M.v[0][1]+M.v[1][1])%mod);
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  map<int64_t, int64_t> data;
  int64_t sum = 0;
  for(int i = 0; i < N; i++) {
    int64_t a;
    cin >> a;
    sum += a;
    if(data.count(a)) {
      data.at(a)++;
    }
    else {
      data[a] = 1;
    }
  }
  int Q;
  cin >> Q;
  for(int i = 0; i < Q; i++) {
    int64_t b, c;
    cin >> b >> c;
    if(data.count(b)) {
      sum += (c - b) * data.at(b);
      cout << sum << endl;
      if(data.count(c)) {
        data.at(c) += data.at(b);
      }
      else {
        data[c] = data.at(b);
      }
      data.erase(b);
    }
    else {
      cout << sum << endl;
    }
  }
}

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

int main()
{
    string s;
    cin >> s;
    ll ans = 0;
    int n = s.size()-1;

    for (int bit = 0; bit < (1 << n); bit++) {
        ll tmp = s[0] - '0';
        for (int i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                ans += tmp;
                tmp = s[i+1]-'0';
            } else {
                tmp *= 10;
                tmp += s[i+1]-'0';
            }
        }
        ans += tmp;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
y,m,d = map(int, input().split('/'))
if y > 2019:
    print('TBD')
elif y == 2019:
    if (m > 4) or (m == 4 and d > 30):
        print('TBD')
    else:
        print('Heisei')
else:
    print('Heisei')


Measured memory_bytes: 2940
n, q = [int(t) for t in input().split()]
procs = []
for i in range(n):
    name, tm = input().split()
    procs.append((name, int(tm)))

curtime = 0
while len(procs) > 0:
    queue = []
    for name, tm in procs:
        if tm <= q:
            curtime += tm
            print(name, curtime)
        else:
            curtime += q
            queue.append((name, tm - q))
    procs = queue



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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    P=LI()
    Q=LI()
    
    
    import itertools
    
    cnt=0
    p=0
    q=0
    for ite in itertools.permutations(range(1,N+1)):
        if P==list(ite):
            p=cnt
        if Q==list(ite):
            q=cnt    
        cnt+=1
        
    print(abs(p-q))
        
        
main()


Measured memory_bytes: 73760
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
const ll INF=1e9+7;
const ll N = 9;
ll n,m,a,b,ans=0;
bool e[N][N];
bool did[N];

bool allgo(){
	bool ok=true;
	FOR(i,1,n+1){
		if(did[i]==false)ok=false;
	}
	return ok;
}

void dfs(ll s,ll f){
	did[s]=true;
	FOR(i,1,n+1){
		if(did[i]==false&&e[s][i]==true){
			did[i]=true;
			if(allgo()&&i==f){
				ans++;
			}
			dfs(i,f);
		}
	}
	did[s]=false;
}

int main(){
	cin>>n>>m;
	FOR(i,0,m){
		cin>>a>>b;
		e[a][b]=e[b][a]=true;
	}
	FOR(i,2,n+1){
		FOR(j,0,n+1)did[j]=false;
		dfs(1,i);
	}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod = int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    ll U=3010;
    ll MOD=998244353;
    ll n,s;cin>>n>>s;
    vector<ll>a(n);
    for (int i = 0; i < n; ++i) {
        cin >>a[i];
    }
    vector<vector<ll>>dp(n+1,vector<ll>(s+1,0));
    ll ans=0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <s+1; ++j) {
            ll cost=(j==0)?1:0;
            dp[i+1][j]+=(dp[i][j]+cost)%MOD;
            dp[i+1][j]%=MOD;
            if(j+a[i]>s)continue;
            dp[i+1][j+a[i]]+=(dp[i][j]+cost)%MOD;
            dp[i+1][j+a[i]]%=MOD;
        }
        ans+=dp[i+1][s];
        ans%=MOD;
//        cout <<ans <<endl;
    }
    cout <<ans <<endl;
    return 0;
}

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

int main()
{
  string s;
  cin >> s;
  int plan1, plan2;
  vector<char> l1(s.size());
  vector<char> l2(s.size());
  plan1 = 0;
  plan2 = 0;
  int i;
  for(i = 0; i < s.size(); i++)
  {
    if(i%2==0)
    {
      l1.at(i) = '0';
      l2.at(i) = '1';
    }
    else
    {
      l1.at(i) = '1';
      l2.at(i) = '0';
    }
  }
  for(i = 0; i < s.size(); i++)
  {
    if(l1.at(i) != s.at(i))
    {
      plan1++;
    }
    if(l2.at(i) != s.at(i))
    {
      plan2++;
    }
  }
  cout << min(plan1, plan2) << endl;
}

Measured memory_bytes: 512
import java.util.*
fun main(args:Array<String>) {
    data class Monster(val x:Long=0L, var hp:Long=0L)
    var (n,d,a) = readLine()!!.split(" ").map { it.toInt() }
    var monster = Array(n){Monster(0,0)}
    /*
    fun createTestSet() {
        n = 200000
        d =  Random.nextInt(1..1000000000)
        a = Random.nextInt(1..1000000000)
        monster = Array(n){Monster(0,0)}
        val s = HashSet<Int>()
        for(i in 0 until n) {
            var x = Random.nextInt(0..1000000000)
            val hp = Random.nextInt(1..1000000000)
            while(s.contains(x)) {
                x = Random.nextInt(1..1000000000)
            }
            s.add(x)
            monster[i] = Monster(x.toLong(), hp.toLong())

        }
    }
     */

    for(i in 0 until n) {
        val (x,h) = readLine()!!.split(" ").map { it.toInt() }
        monster[i] = Monster(x.toLong(), h.toLong())
    }
    monster.sortBy { it.x }
    var answer = 0L
    var acc = 0L
    val q = LinkedList<Pair<Long,Long>>()
    for(i in 0 until n) {
        var (x, h) = monster[i]
        while(q.isNotEmpty() && q.peekFirst()!!.first + d * 2 < x) {
            val p = q.pollFirst()
            acc -= p.second
        }
        h -= acc
        if(h <= 0) continue
        var cnt = h / a //+ min(h%a, 1)
        if((h%a) >= 1) {
            cnt += 1
        }
        q.add(x to  cnt * a)
        acc += cnt * a
        answer += cnt
    }
    println(answer)
    /*
    var nCase = 1000
    repeat(nCase) {
        createTestSet()
    }
     */
    // x 의 범위가 무지막지하게 크다.
    //


}

Measured memory_bytes: 127492
main(){double a,b,c,d,e,f;for(;~scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);printf("%.3f %.3f\n",a=(c-b*d)/a,d=(a*f-c*d)/(a*e-b*d)));}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	int L, R;
	for (int tt = 0; ; ++ tt) {
		int x;
		if (tt < 3) {
			x = (tt*N)/3;
		} else {
			if (tt == 3) {
				int x1 = N/3;
				int x2 = (2*N)/3;
				if ((x1%2 == 0 && A[0] != A[x1]) || (x1%2 != 0 && A[0] == A[x1])) {
					L = 0; R = x1;
				} else if (((x2-x1)%2 == 0 && A[x1] != A[x2]) || ((x2-x1)%2 != 0 && A[x1] == A[x2])) {
					L = x1; R = x2;
				} else {
					L = x2; R = N;
				}
			} else {
				if (((x-L)%2 == 0 && A[L] == A[x]) || ((x-L)%2 != 0 && A[L] != A[x])) {
					L = x;
				} else {
					R = x;
				}
			}
			x = ((L + R) / 2) % N;
		}
		cout << x << endl;
		string s;
		cin >> s;
		if (s == "Vacant") break;
		if (s == "Male") A[x] = 1; else A[x] = 2;
	}
}


Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; --i)
#define FOR(i, n, m) for (int i = m; i < n; i++)
#define MM(i, n, m) for (int i = m; i <= n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

typedef long long ll;
/**
 * C問以降は ll を使う.
 * double型にするのを忘れない.
 * nC2の求め方 (1/2)*n*(n-1)
 * vector<型> 変数名(要素数, 初期値)
*/
int main()
{
  int x, a, b;
  cin >> x >> a >> b;
  cout << (x-a)%b << endl;
    return 0;
}

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

int main(void){
    int n;
    cin>>n;
    pair<int,int> rl[n];
    for(int i=0; i<n;i++){
        int x,l;
        cin>>x>>l;
        rl[i] = make_pair(x+l,x-l);
    }

    sort(rl,rl+n);

    int right = -1000000000,ans=0;
    for(int i=0;i<n;i++){
        if(right <= rl[i].second){
            ans ++;
            right = rl[i].first;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
#define mod 1000000007
#define MOD 1000000037
#define mod1 998244353
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define INF 1e18
#define common cout << "Case #" << w+1 << ": "  


vector<set<int> >v;
int cnt=0;
vector<bool>vis;
int ans=1;


void dfs(int u)
{
    vis[u]=true;
    cnt+=1;
    set<int>:: iterator it;
    for(it=v[u].begin();it!=v[u].end();it++)
    {
        if(!vis[*it])
            dfs(*it);
    }
}

int main()
{
    fastio;
    int n,m;
    cin >> n >> m;
    v.resize(n);
    vis.resize(n,false);
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin >> x >> y;
        x-=1;y-=1;
        v[x].insert(y);
        v[y].insert(x);
    }
    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        {
            cnt=0;
            dfs(i);
            ans=max(ans,cnt);
        }
    }
    cout << ans << endl;
}

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

int main() {
  int N;
  cin >> N;
  
  vector<int> point(N);
  for (int i = 0; i < N; i++) {
    cin >> point.at(i);
  }
  if (N % 2 == 1) {
    point.push_back(0);
  }
  sort(point.begin(), point.end());
  reverse(point.begin(), point.end());
  
  int asum = 0, bsum = 0;
  for (int i = 0; i < N; i += 2) {
    asum += point.at(i);
    bsum += point.at(i + 1);
  }
  
  int answer;
  answer = asum - bsum;
  cout << answer << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using vll = vector<ll>;

void solve();

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

  solve();

  return 0;
}

#define ini(...)   \
  int __VA_ARGS__; \
  in(__VA_ARGS__)

#define inl(...)  \
  ll __VA_ARGS__; \
  in(__VA_ARGS__)

#define ins(...)      \
  string __VA_ARGS__; \
  in(__VA_ARGS__);

void in() {}
template <typename T, class... U>
void in(T& t, U&... u) {
  cin >> t;
  in(u...);
}

void out() {
  cout << endl;
}
template <typename T, class... U>
void out(const T& t, const U&... u) {
  cout << t;
  if (sizeof...(u))
    cout << " ";
  out(u...);
}

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

void solve();
#ifndef ONLINE_JUDGE
#include "./lib.hpp"
#endif

void solve() {
    ins(O, E);
    rep(i, O.size()) {
        cout << O[i];
        if (i < E.size())
            cout << E[i];
    }
    out();
}


Measured memory_bytes: 3652
mod=10**9+7
N,M=map(int,input().split())
alist = [True]*(N+1)
for i in range(M):
  alist[int(input())] = False

#print(alist)
reslist = [0]*(N+1)
reslist[0] = 1
if alist[1]:
  reslist[1] = 1

for i in range(2,N+1):
  if alist[i]:
    reslist[i] = (reslist[i-2]+reslist[i-1])%mod
  else:
    reslist[i] = 0
    
#print(reslist)
print(reslist[N])

Measured memory_bytes: 46296
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

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

signed main(){
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i, n) cin >> p[i];

    vector<int> len(n+1);
    rep(i, n){
        len[p[i]] = len[p[i]-1]+1;
    }

    int max = *max_element(len.begin(), len.end());
    cout << n - max << endl;

    return 0;
}


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

using namespace std;

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

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());

    int64_t ans = 0;
    for(int i=0; i<N; i++) {
        ans += (int64_t)distance(A.begin(), lower_bound(A.begin(), A.end(), B[i])) * (int64_t)distance(upper_bound(C.begin(), C.end(), B[i]), C.end());
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 60;
const long double PI = acosl(-1.0);
constexpr long double EPS = 1e-11;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
ll n;
cin >> n;
  if(n%1000==0)cout<<0<<endl;
  else
cout << 1000-(n % 1000)  << endl;
}

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

using ll = long long;
#define repi(n) for (int i = 0; i < n; i++)
#define repj(n) for (int j = 0; j < n; j++)
#define repk(n) for (int k = 0; j < n; k++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (auto i = a; i < b; i++)
#define repv(itr) for (auto&& v : itr)
const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
template <typename T>
T minptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i < *re) re = i;
  }
  return re;
}
template <typename T>
T maxptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i > *re) re = i;
  }
  return re;
}
int __vmax(int x) {
  return INT_MAX;
}
double __vmax(double x) {
  return 1e+300;
}
ll __vmax(ll x) {
  return LLONG_MAX;
}
int __vmin(int x) {
  return INT_MIN;
}
double __vmin(double x) {
  return -1e+300;
}
ll __vmin(ll x) {
  return LLONG_MIN;
}
template <typename T>
vector<T> lis(T begin, T end, bool allowequal = false, bool lds = false) {
  using V = typename iterator_traits<T>::value_type;
  int n = end - begin;
  vector<V> a(n, lds ? __vmin(*begin) : __vmax(*begin));
  vector<int> id(n);
  if (lds && allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (lower_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (lds) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (upper_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = upper_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  } else {
    for (int i = 0; i < n; i++) {
      id[i] = lower_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  }
  int m = *maxptr(id.begin(), id.end());
  vector<T> re(m + 1);
  for (int i = n - 1; i >= 0; i--) {
    if (id[i] == m) re[m--] = begin + i;
  }
  return re;
}

int x[100100];
int y[100100];
int main() {
  int n, m;
  cin >> n >> m;
  repi(m) cin >> x[i];
  sort(x, x + m);
  repi(m - 1) y[i] = x[i + 1] - x[i];
  sort(y, y + m - 1);
  int re = 0;
  repi(m - n) re += y[i];
  cout << re << endl;
}


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

int main()
{
	int N, M;
	cin >> N >> M;
	vector<vector<pair<int, int>>> all(N);
	for (int i = 0; i < M; i++) {
		int P, Y;
		cin >> P >> Y; --P;
		all[P].emplace_back(Y, i);
	}
	vector<int> x(M), y(M);
	for (int i = 0; i < N; i++) {
		sort(all[i].begin(), all[i].end());
		for (int j = 0; j < (int)all[i].size(); j++) {
			int Y, id;
			tie(Y, id) = all[i][j];
			x[id] = i + 1;
			y[id] = j + 1;
		}
	}
	for (int i = 0; i < M; i++) {
		string a = to_string(x[i]);
		a = string(6 - a.size(), '0') + a;
		string b = to_string(y[i]);
		b = string(6 - b.size(), '0') + b;
		cout << a + b << endl;
	}
	return 0;
}


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

using namespace std;

int main() {
  int ans[11];
  int n = 0;
  string input; cin >> input;

  for (int i = 0; i < input.size(); i++) {
    if(input[i] == 'B') {
      if(n!=0) n--;
    }
    else {
      ans[n] = int(input[i] - '0');
      n++;
    }
  }

  for (int i = 0; i < n; i++) {
    cout << ans[i];
  }
  cout << endl;
}


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

const int mod = 1e9 + 7;
int h, w;
char grid[1005][1005];
int dp[1005][1005];

inline void madd(int &a, int b){
	a += b;
	if (a > mod) a -= mod;
}

void solve(){
	dp[1][1] = 1;
	for (int i = 1; i <= h; i++){
		for (int j = 1; j <= w; j++){
			madd(dp[i][j], dp[i-1][j]);
			madd(dp[i][j], dp[i][j-1]);
			if (grid[i][j] == '#') dp[i][j] = 0;
		}
	}
	printf("%d\n",dp[h][w]);
}
int main(){
	scanf("%d %d",&h,&w);
	for (int i = 1; i <= h; i++)
		scanf("%s",grid[i]+1);
	solve();
	return 0;
}


Measured memory_bytes: 5120
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt();
		int M = sc.nextInt();
		ArrayList<ArrayList<Integer>> plusS = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> plusE = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> minusS = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> minusE = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < N + 2; ++i) {
			plusS.add(new ArrayList<Integer>());
			plusE.add(new ArrayList<Integer>());
			minusS.add(new ArrayList<Integer>());
			minusE.add(new ArrayList<Integer>());
		}
		for (int i = 0; i < M; ++i) {
			int A = Integer.parseInt(sc.next());
			int B = Integer.parseInt(sc.next());
			int X = Integer.parseInt(sc.next());
			plusS.get(A).add(B);
			minusS.get(A).add(B + 1);
			plusE.get(A + X + 1).add(B);
			minusE.get(A + X + 1).add(B + 1 + X + 1);
		}
		int[][] psum = new int[2][N + 2];
		int[][] msum = new int[2][N + 2];
		int[] sum = new int[N + 2];
		int ans = 0;
		int t = 1;
		for (int i = 1; i <= N; ++i) {
			Arrays.fill(psum[t], 0);
			Arrays.fill(msum[t], 0);
			Arrays.fill(sum, 0);
			for (int j : plusS.get(i)) {
				psum[t][j]++;
			}
			for (int j : plusE.get(i)) {
				psum[t][j]--;
			}
			for (int j : minusS.get(i)) {
				msum[t][j]++;
			}
			for (int j : minusE.get(i)) {
				msum[t][j]--;
			}
			for (int j = 1; j <= i; ++j) {
				psum[t][j] += psum[1 - t][j];
				msum[t][j] += msum[1 - t][j - 1];
			}
			for (int j = 1; j <= i; ++j) {
				sum[j] = sum[j - 1] + psum[t][j] - msum[t][j];
				if (sum[j] > 0) ++ans;
			}
			t = 1 - t;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 223900
# nCk 前処理メモ化
MOD = 10 ** 9 + 7
N = 2000
@fac = [1, 1]
@inv = [1, 1]
@finv = [1, 1]

(2..N).each do |i|
  @fac[i] = @fac[i - 1] * i % MOD
  @inv[i] = MOD - @inv[MOD % i] * (MOD / i) % MOD
  @finv[i] = @finv[i - 1] * @inv[i] % MOD
end

def nCk(n, k)
  return 0 if n < k || n < 0 || k < 0
  @fac[n] * (@finv[k] * @finv[n - k] % MOD) % MOD
end

def repeated_nCk(n, k)
  # 仕切りのイメージで
  nCk(n + k - 1, n - 1) % MOD
end

n, blue = gets.split.map(&:to_i)
red = n - blue
ans = []
(1..blue).each do |count|
  ans << nCk(red + 1, count) * repeated_nCk(count, blue - count)
end
ans.each { |a| puts a % MOD }


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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int A[100]={101};
  for(int i=1; i<=100; i++) {
    A[i-1]=a*i%b;
  }
  for(int i=0; i<100; i++) {
    if(A[i]==c) {
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}

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

int main()
{
	int a[5],mark;
	
	rep(5){
		cin>>a[i];
		if(a[i]==0 && i>0){
			a[i]=a[i-1]+1;
			mark=i;
		}
		else if(a[i]==0 && i==0){
			a[i]=1;
			mark=i;
		}
	}
	cout<<a[mark];
	return 0;
}

Measured memory_bytes: 3516
N = int(input())
A = [0] + list(map(int, input().split())) + [0]
cost = []
for i in range(N + 1):
    cost.append(abs(A[i + 1] - A[i]))
scost = sum(cost)
for i in range(N):
    print(scost - cost[i] - cost[i + 1] + abs(A[i + 2] - A[i]))


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

int main(){
    int n;
    cin >> n;
    vector<tuple<string,int,int>> sp;
    for(int i=1;i<=n;i++){
        string s;
        int p;
        cin >> s >> p;
        sp.emplace_back(s,-p,i);
    }
    sort(begin(sp),end(sp));
    // sort(All(sp),[]( const auto &x, const auto &y){
    //         //第一要素が同一ならば第二要素の大きい方を返す
    //         return get<0>( x ) == get<0>( y ) ? get<1>( x ) > get<1>( y ) : get<0>( x ) < get<0>( y );
    // });
    for(int i=0;i<n;i++){
        cout <<get<2>(sp[i])<<endl;
    }


}

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

int main() {
    //
    int num;
    long double sum = 0;

    cin >> num;
    long double tmp;
    string str;
    for (int i = 0; i < num; i++) {
        cin >> tmp >> str;
        if (str == "JPY") {
            sum += tmp;
        } else {
            tmp *= 380000;
            sum += tmp;
        }
    }

    cout << setprecision(10) << sum << endl;
    //
}


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

int main(){
    string a, b, c, d;
    int n;
    cin >> a >> b;
        
    if ( min(a, b) == a ){
            c = a;
            d = b;
        }
        
    else {
        c = b;
        d = a;
        }
    stringstream geeks(d);
    geeks >> n;
    for (int x = 0; x < n; x++){
        cout << c;
    }
    cout << endl;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  ll n, x;
  cin >> n >> x;
  vector<ll> a(n);
  REP(i, n) { cin >> a[i]; }
  ll ans = 0;
  FOR(i, 1, n) {
    ll s = a[i] + a[i - 1];
    ll d = max(s - x, 0LL);
    ans += d;
    a[i] = max(a[i] - d, 0LL);
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024