akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
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;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

template<typename T> struct edge{
    int from, to; T cost;
    edge(int f, int t, T c): from(f), to(t), cost(c){}
};
 
template<typename T> struct Graph{
    vector<vector<edge<T>>> G;
    int n;
 
    Graph(int n_): n(n_){
        G.resize(n);
    }
 
    void add_edge(int f, int t, T c){
        G[f].emplace_back(f, t, c);
    }
};

template<typename T> vector<T> dijkstra(Graph<T> &gr, int s){
    using state = pair<T, int>;
    priority_queue<state, vector<state>, greater<state>> que;
    vector<T> d(gr.n, numeric_limits<T>::max());
    d[s] = 0;
    que.emplace(0, s);
    while(!que.empty()){
        state p = que.top(); que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        for(edge<T> &e : gr.G[v]){
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.emplace(d[e.to], e.to);
            }
        }
    }
    return d;
}

int n, m, s, g1, g2;

void solve(){
    Graph<int> gr(n), gr_rev(n);
    rep(i, m){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        --a; --b;
        gr.add_edge(a, b, c);
        gr_rev.add_edge(b, a, c);
    }
    auto ds = dijkstra(gr, s), d1 = dijkstra(gr_rev, g1), d2 = dijkstra(gr_rev, g2);
    lint ans = mod;
    rep(i, n){
        chmin(ans, (lint)ds[i] + d1[i] + d2[i]);
    }
    printf("%lld\n", ans);
}

int main(){
    while(scanf("%d%d%d%d%d", &n, &m, &s, &g1, &g2) && n){
        --s; --g1; --g2;
        solve();
    }
}


Measured memory_bytes: 3280
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int mod = 1000000007;
const int INF = 1001001001;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    int n;
    cin >> n;
    vector<P> a(n);
    rep(i,n){
        cin >> a[i].first;
        a[i].second = i+1;
    }
    sort(a.begin(),a.end());
    rep(i,n){
        cout << a[i].second << endl;
    }
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) #x "=" << x << " "
#define fore(i,a,b) for(int i=a,gon=b;i<gon;++i)
#define pb push_back
#define F first
#define S second
typedef double lf;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        //freopen("out.txt", "w", stdout);
    #else
        #define endl '\n'
    #endif
    string s, ans = "";
    cin >> s;
    int n = s.size();
    fore(i,0,n) {
        if (s[i] != 'B') ans.pb(s[i]);
        else if (ans.size()) ans.pop_back();
    }
    cout << ans << '\n';
}


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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;

int main()
{
	int n,tg;
	cin >> n;
	vi a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	if (a[0] == 2) {
		cout << 1 << endl;
		return 0;
	}
	else {
		tg = a[0] - 1;
	}

	for (int i = 0; i < 100000; i++) {
		if (a[tg] == 2) {
			cout << i + 2 << endl;
			return 0;
		}
		tg = a[tg] - 1;
	}

	cout << -1 << endl;
	return 0;
}

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


int main() {
    int n;
    cin >> n;
    set<char> st;
    for (int i = 0; i < n; i++) {
        char drop;
        cin >> drop;
        st.insert(drop);
    }

    if (st.size() == 3) cout << "Three" << endl;
    else cout << "Four" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}
void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}

int main(){
	int n,m;
	int i,j,k;
	int a,b,c;
	cin>>a>>b;
	if(a<10 && b<10)cout<<a*b<<endl;
	else cout<<-1<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>

using namespace std;


int main(void)
{
	int i, j, k;
	int n; //??°??????????????°
	int x[1000], y[1000], s[1000];
	int mx = 0;
	int temp;
	int count = 0; // x?????¨???s???????????????????????°
	vector<pair<int, int>> z; //??°???????¨????

	for (i = 0; ; i++) {
		cin >> x[i] >> y[i] >> s[i];
		if (x[i] == 0 && y[i] == 0 && s[i] == 0) {
			break;
		}

	}
	n = i;
	for (i = 0; i < n; i++) {
		mx = 0;

		for (j = 1; j < s[i]; j++) {
			for (k = j; k < s[i]; k++) {
				temp = j * (100 + x[i]) / 100 + k * (100 + x[i]) / 100;
				if (temp == s[i]) {
					temp = j * (100 + y[i]) / 100 + k * (100 + y[i]) / 100;
					if (temp > mx) {
						mx = temp;
					}
				}
			}

	
		}
		cout << mx << endl;


	}




	return (0);
}

Measured memory_bytes: 3076
#include<iostream>
#include<tuple>
#include<vector>
#include<set>
#include<bitset>
#include<algorithm>
using namespace std;

typedef tuple<vector<int>, int, int> Hint;
enum{TRY, HIT, BLOW};

const int NUMBERS = 10;

vector<vector<int>> subset_combination(int n, int k, vector<int> number) {
    vector<vector<int>> result;
    unsigned long long int S = (1 << k) - 1;
    unsigned long long int E = ~((1 << n) - 1);
    while(!(S & E)) {
        bitset<NUMBERS> flag(S);
        vector<int> v;
        for(int i = 0; i < n; i++) if(flag[i]) v.push_back(number[i]);
        result.push_back(v);
        unsigned long long int smallest = S & -S;
        unsigned long long int ripple = S + smallest;
        unsigned long long int nsmallest = ripple & -ripple;
        S = ripple | (((nsmallest / smallest) >> 1) - 1);
    }
    return result;
}

vector<vector<int>> check(vector<int> v, const vector<Hint>& hint) {
    sort(v.begin(), v.end());
    vector<vector<int>> result;
    do {
        bool ok = true;
        for(const auto& h: hint) {
            int hit = 0, blow = 0;
            int count[10] = {0};
            for(const auto& n: get<TRY>(h)) count[n]++;
            for(int i = 0; i < v.size(); i++) {
                if(v[i] == get<TRY>(h)[i]) hit++;
                else if(count[v[i]]) blow++;
            }
            if(hit != get<HIT>(h) || blow != get<BLOW>(h)) {
                ok = false;
                break;
            }
        }
        if(ok) {
            result.push_back(v);
            if(result.size() > 1) return result;
        }
    } while (next_permutation(v.begin(), v.end()));
    return result;
}

int main() {
    int L, H;
    vector<Hint> hint;
    vector<vector<int>> candidate;
    while(cin >> L >> H, L | H) {
        hint.resize(H);
        for(auto& element: hint) {
            string t;
            int h, b;
            cin >> t >> h >> b;
            vector<int> number;
            for(auto& n: t) number.push_back(n - '0');
            element = Hint(number, h, b);
        }

        vector<int> all = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        candidate = subset_combination(NUMBERS, L, all);

        vector<int> answer;
        bool ok = true;
        for(auto& v: candidate) {
            vector<vector<int>> result = check(v, hint);
            if(result.size() > 1) ok = false;
            if(result.size() == 1) {
                if(answer.size()) ok = false;
                else answer = *result.begin();
            }
            if(!ok) break;
        }

        if(ok && answer.size()) {
            for(const auto& n: answer) cout << n;
            cout << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

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

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

    std::vector<int> d(N);
    for (int i = 0; i < N; i++) {
        std::cin >> d[i];
    }

    std::sort(d.begin(), d.end());

    std::cout << d[N/2] - d[N/2 - 1] << std::endl;
    
    return 0;
}

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

int main(){
    int n, k;
    cin >> n >> k;
    if(n % k == 0){
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair< int, int > pii;
typedef pair< pii, int > ppi;
#define fill(a,b) memset(a,b,sizeof(a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int inf = 0x3f3f3f3f;// (int)3e18;
const int maxn = 100001;



int main(){
        _
        int n; cin >> n;
        vi b(n-1),a(n);
        rep(i,n-1)cin >> b[i], a[i] = b[i];
        a[n-1] = maxn;

        rep(i,n-1){
            a[i+1]=min(a[i+1],b[i]);
        }
        ll sum = 0;
        rep(i,n){
            sum+=a[i];
        }
        cout<<sum<<endl;

return 0;
}



Measured memory_bytes: 256
--???????????????????????????????????°

--??°????????????????´?????????£??????????????´??°??????????????§??????????????????????????????????????????????????´??°???i??¨???????????°?????????j????????\??????????´???§i?????????????????¨??????boole??¢??°
--???????????????????????¨???????????¢??°????????°??????f(i,j)=f(i-m_j,j+1) or f(i,j+1)??§????????§??????????????????,j????????§???????????????????????¨?????¨?????????0??????????????¨?????????
--???????????£????¬?????????°??§?§£??????

solver::Int->[Int]->Bool
solver x  (w:ws)= ((x-w>=0)&&(solver (x-w) ws))||(solver x ws)
solver 0  _     = True
solver _  _     = False

prints::[Bool]-> IO()
prints [] = return()
prints (x:xs) =do
  putStr (if x then "yes" else "no")
  putStr "\n"
  prints xs

main::IO()
main =do
  _<-getLine
  ws<-getLine
  let weights = map read (words ws)::[Int]
  _<-getLine
  is<-getLine
  let items   = map read (words is)::[Int]
  prints (map (\x -> solver x weights) items)

Measured memory_bytes: 5388
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
const int inf=1000000007;
const int MOD=1000000007;

struct UnionFind{
    vector<int> par;
    vector<int> group;
    UnionFind(int n) : par(n){
      for(int i=0;i<n;i++)par[i]=i;
    }
    int root(int x){
      if(par[x]==x) return x;
      return par[x]=root(par[x]);
    }
    void Net(int n){
      for(int i=0;i<n;i++){
        group.push_back(0);
      }
      for(int i=0;i<n;i++){
        group[root(i)]++;
      }
    }
    int size(int i){
        return group[root(i)];
    }
    void unite(int x,int y){
      int rx=root(x);
      int ry=root(y);
      if(rx==ry) return;
      par[rx]=ry;
    }
    bool same(int x, int y){
      int rx=root(x);
      int ry=root(y);
      if(rx==ry) return 1;
      return 0;
    }
  };
  struct Man{
      vector<int> ff;
      vector<int> bl;
  };
signed main(){
  int n,m,k;
  cin>>n>>m>>k;
  vector<Man> man(n);
  UnionFind tree(n);
  rep(i,m){
      int a,b;cin>>a>>b;
      a--;b--;
      man[a].ff.push_back(b);
      man[b].ff.push_back(a);
      tree.unite(a,b);
  }
  rep(i,k){
      int a,b;cin>>a>>b;
      a--;b--;
      man[a].bl.push_back(b);
      man[b].bl.push_back(a);
  }
  tree.Net(n);
  rep(i,n){
      int res=tree.size(i)-1;
      int fn=man[i].ff.size();
      int bn=man[i].bl.size();
      rep(j,fn){
          if(tree.same(i,man[i].ff[j]))res--;
      }
      rep(j,bn){
          if(tree.same(i,man[i].bl[j]))res--;
      }
      cout<<res<<endl;
  }
  return 0;
}


Measured memory_bytes: 13048
#include <bits/stdc++.h>
#define Int int64_t
#define pb push_back
using namespace std;
const int MAXN=500005;
vector<int> A(MAXN);
Int N,M,X,Y,B,K,Z,T;
int main()
{
   cin>>N;
   cout<<(1000-(N%1000))%1000<<"\n";
}

Measured memory_bytes: 4956
// C - Attention
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int N; scanf("%d\n",&N);
	vi W(N+1);
	rp(i, 0, N) W[i+1] = W[i] + (getchar()=='W');
	int mini = INT_MAX;
	rp(leader, 1, N+1)
		mini = min(mini, W[leader-1] + (N-leader)-(W[N]-W[leader]));
	cout<< mini <<endl;
}

Measured memory_bytes: 1536
import java.util.*;

class Main{
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int a[] = new int[3];

    a[0] = scan.nextInt();
    a[1] = scan.nextInt();
    a[2] = scan.nextInt();
    int tmp;

    for(int i=0 ; i<2 ; i++){
      for(int j=2 ; j>i ; j--){
        if(a[j-1] > a[j]){
          tmp = a[j-1];
          a[j-1] = a[j];
          a[j] = tmp;
        }
      }
    }
    System.out.println(a[0] + " " + a[1] + " " + a[2]);
  }
}

Measured memory_bytes: 26132
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
#define rep(i,n) for (int i = 1; i < (n); i++) 
#define out(n) cout << n << endl;

int main() {
    int k;
    cin >> k;

    string s;

    cin >> s;

    if(s.size() <= k){
        out(s);
    }else{
        for (int i = 0; i < k; i++)
        {
            cout << s[i];
        }
        cout <<"..." << endl;
    }

}

Measured memory_bytes: 3640
# S -> S
# c -> c
# cc -> S

# count(S) > count(c)/2 -> count(Scc) = count(c)/2
# count(S) < count(c)/2 -> count(S) + (count(c) - count(S)*2)/4)

N, M = map(int, raw_input().split())
if N >= M / 2:
  print M / 2
else:
  print N + (M - N * 2) / 4

Measured memory_bytes: 2568
#include <iostream>

using namespace std;

int main()
{
    
    int a, b, temp, i;
    for(i=1; i<=3000; i++)
    {
        
        cin >> a >> b;
        
        if (a == 0 && b == 0)
                break;
        
        if(a > b)
        {
            temp = a;
            a = b;
            b = temp;
        }
        cout << a << " " << b << endl;

    }
}


Measured memory_bytes: 3004
#include <string>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i =0;i < n;i++){
        cin >> a[i];
    }
    int j=0,ans,cnt=0;
    bool q = false;
    for(int i =0;i<n;i++){
        ans = a[j];
        j = ans-1;
        cnt++;
        if(ans == 2){
            q = true;
            break;
        }
    }
    if(q){
        cout << cnt;
    }else{
        cout << -1;
    }
    
    
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;

ll Pow3T[16];
ll Pow3(int n)
{
    if (Pow3T[n] != 0) return Pow3T[n];
    if (n == 0) return Pow3T[n]=1;
    else if (n==1) return Pow3T[n]=3;
    else if (n%2==0) {
        ll Tmp = Pow3(n/2);
        return Pow3T[n]=Tmp*Tmp;
    } else {
        return Pow3T[n]=3 * Pow3(n-1);
    }
}

int main()
{
    while (1) {
        int N, M;
        cin >> N >> M;
        if (N == 0 && M == 0) break;
        ll S = 0LL;
        for (int i = 0; i < 3; ++i) {
            int K;
            cin >> K;
            for (int k = 0; k < K; ++k) {
                int P;
                cin >> P;
                --P;
                S += i * Pow3(P);
            }
        }

        vector<ll> D(Pow3(N), -1);
        queue<ll> Q;
        Q.push(S);
        D[S] = 0;
        int Res = -1;
        while (!Q.empty()) {
            ll Now = Q.front(); Q.pop();
            vector<ll> vNext;

            {
                int k = N-1;
                while (Now/Pow3(N-1) == (Now/Pow3(k))%3) {--k; if (k==-1) break;}
                if (k == -1) {
                    if (Now%3 == 1) ;
                    else {
                        Res = D[Now];
                        break;
                    }
                }

                ll Tmp = Now;
                if (Now/Pow3(N-1) == 0) {
                    Tmp = Now + Pow3(N-1);
                    vNext.push_back(Tmp);
                    if ((Now/Pow3(k))%3 == 1) {
                        Tmp = Now + Pow3(k);
                        vNext.push_back(Tmp);
                    } else if ((Now/Pow3(k))%3 == 2) {
                        Tmp = Now - Pow3(k);
                        vNext.push_back(Tmp);
                    }
                }
                if (Now/Pow3(N-1) == 1) {
                    Tmp = Now - Pow3(N-1);
                    vNext.push_back(Tmp);
                    Tmp = Now + Pow3(N-1);
                    vNext.push_back(Tmp);
                }
                if (Now/Pow3(N-1) == 2) {
                    Tmp = Now - Pow3(N-1);
                    vNext.push_back(Tmp);
                    if ((Now/Pow3(k))%3 == 0) {
                        Tmp = Now + Pow3(k);
                        vNext.push_back(Tmp);
                    } else if ((Now/Pow3(k))%3 == 1) {
                        Tmp = Now - Pow3(k);
                        vNext.push_back(Tmp);
                    }
                }

                int d = D[Now] + 1;
                if (d > M) continue;
                for (int i = 0; i < vNext.size(); ++i) {
                    ll TmpS = vNext[i];
                    if (D[TmpS] == -1) {
                        D[TmpS] = d;
                        Q.push(TmpS);
                    }
                }
            }
        }
        cout << Res << endl;
    }

    return 0;

}


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

bool vector_eq(const std::vector<int> &a, const std::vector<int> &b) {
    for(uint32_t i = 0; i < a.size(); ++i) {
        if(a[i] != b[i]) {
            return false;
        }
    }
    return true;
}

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

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

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

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

    int64_t p_pos, q_pos;
    int64_t pos = 0;
    int found = 0;

    do {
        ++pos;
        if(vector_eq(ps, v)) {
            p_pos = pos;
            ++found;
        }
        if(vector_eq(qs, v)) {
            q_pos = pos;
            ++found;
        }
        if(found >= 2) {
            break;
        }
    } while(std::next_permutation(v.begin(), v.end()));

    std::cout << std::abs(p_pos - q_pos);

    return 0;
}


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

#define ll long long
const int siz = 407;
const ll MAXN = (ll)1e18 + 7LL;

int n;
ll pref [siz];
ll dp [siz][siz];

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%lld",&pref[i]);
        pref[i] += pref[i - 1];
    }

    for(int d = 1; d <= n; d++){
        for(int i = 1; i <= n - d; i++){
            dp[i][i + d] = MAXN;
            for(int j = i; j < i + d; j++){
                ll w = dp[i][j] + dp[j + 1][i + d] + pref[i + d] - pref[i - 1];
                dp[i][i + d] = min( dp[i][i + d], w );
            }
        }
    }
    printf("%lld\n",dp[1][n]);
}


Measured memory_bytes: 1536
from collections import Counter
def p_fact(n,a):
  m=n
  i=2
  while n>1:
    if i>m**.5 and n!=1:
      a.append(n)
      break
    if n%i==0:
      n//=i
      a.append(i)
    else:i+=1  
  return a
n=int(input())
mod=10**9+7
a=[]
for i in range(2,n+1):
  a+=p_fact(i,[])
ans=1
for i in Counter(a).values():
  ans=ans*(i+1)%mod
print(ans%mod)

Measured memory_bytes: 9620
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-12;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

long long int power(long long int x, long long int n, long long int M) {
	long long int ret = 1;
	long long int by = x;
	while (n) {
		if (n & 1) {
			ret *= by;
			ret %= M;
		}
		by *= by;
		by %= M;
		n >>= 1;
	}
	return ret;
}

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

	cin >> N >> L >> R;
	long long int ans = power(2, N, MOD) + MOD - 1;
	ans %= MOD;
	ans += MOD;
	long long int minus = 1;
	for (int i = 1; i <= L; i++) {
		minus *= N - i + 1;
		minus %= MOD;
		minus *= power(i, MOD - 2, MOD);
		minus %= MOD;
	}
	ans -= minus;
	minus = 1;
	ans += MOD;
	for (int i = 1; i <= R; i++) {
		minus *= N - i + 1;
		minus %= MOD;
		minus *= power(i, MOD - 2, MOD);
		minus %= MOD;
	}
	ans -= minus;
	ans %= MOD;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
NH = input().split()
N = int(NH[0])
H = int(NH[1])
a = []
b = []
for v in range(N):
    L = input().split()
    a.append(L[0])
    b.append(L[1])
a = list(map(int, a))
b = list(map(int, b))
a.sort(reverse = True)
b.sort(reverse = True)
c = 0
count = 0
while c < H:
    if len(b) > 0 and a[0] < b[0]:
        c = c + b.pop(0)
        count = count + 1 
    else:
        break
if c < H:
    count = count -(-(H - c)//a[0])
print(count)

Measured memory_bytes: 25064
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    A =list(map(int, input().split()))

    all_gcd = A[0]
    max_num = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
        max_num = max(max_num, a)
    if all_gcd != 1:
        print("not coprime")
        return

    # エラトステネスの篩でmin_prime[i] = (iを割り切る最小の素数)を記録する
    min_prime = [i for i in range(max_num + 1)]
    for p in range(2, int(max_num**0.5) + 1):
        if min_prime[p] != p: continue
        for i in range(2 * p, max_num + 1, p): min_prime[i] = p

    # Aの要素で出てきた素因数をusedに記録
    used = [0] * (max_num + 1)
    for a in A:
        while a > 1:
            p = min_prime[a]
            if used[p]:
                print("setwise coprime")
                return
            while a % p == 0: a //= p
            used[p] = 1
    print("pairwise coprime")




if __name__ == "__main__":
    main()


Measured memory_bytes: 216708
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,m;
int x[MAXN],y[MAXN];
vector<P> v;
vector<int> v1,v2;
int dp[MAXN];
int bit[MAXN+1];
void add(int &a,int b) {a+=b; if(a>=MOD) a-=MOD;}
int sum(int i)
{
    int s=0;
    while(i>0)
    {
        add(s,bit[i]);
        i-=i&-i;
    }
    return s;
}
void Add(int i,int x)
{
    while(i<=n)
    {
        add(bit[i],x);
        i+=i&-i;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&x[i]);
    for(int i=0;i<m;i++) scanf("%d",&y[i]);
    int now=0;
    for(int i=0;i<m-1;i++)
    {
        while(i==0&&now<n&&x[now]<y[i]) now++;
        while(now<n&&x[now]>y[i]&&x[now]<y[i+1])
        {
            v.push_back(P(x[now]-y[i],y[i+1]-x[now]));
            v1.push_back(x[now]-y[i]);v2.push_back(y[i+1]-x[now]);
            now++;
        }
    }
    sort(v1.begin(),v1.end());v1.erase(unique(v1.begin(),v1.end()),v1.end());
    sort(v2.begin(),v2.end());v2.erase(unique(v2.begin(),v2.end()),v2.end());
    for(int i=0;i<(int)v.size();i++)
    {
        v[i].F=lower_bound(v1.begin(),v1.end(),v[i].F)-v1.begin()+1;
        v[i].S=lower_bound(v2.begin(),v2.end(),v[i].S)-v2.begin()+1;
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    now=0;
    while(now<(int)v.size())
    {
        int last=now;
        while(now<(int)v.size()&&v[now].F==v[now+1].F) now++;
        for(int i=last;i<=now;i++) dp[i]=sum(v[i].S-1)+1;
        for(int i=last;i<=now;i++) Add(v[i].S,dp[i]);
        now++;
    }
    int ans=0;
    for(int i=0;i<(int)v.size();i++) add(ans,dp[i]);
    add(ans,1);
    printf("%d\n",ans);
    return 0;
}



Measured memory_bytes: 3448
#include <bits/stdc++.h>
using namespace std;
const int M = 100001;
int n, i, j, ans[M][4];
int main ()
{
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= 3; j++) cin >> ans[i][j];
    }
    for(i = 2; i <= n; i++)
    {
        ans[i][1] += max(ans[i-1][2], ans[i-1][3]);
        ans[i][2] += max(ans[i-1][1], ans[i-1][3]);
        ans[i][3] += max(ans[i-1][2], ans[i-1][1]);
    }
    cout << max(ans[n][1], max(ans[n][2], ans[n][3])) << endl;
}

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

if A == B:
    if C == A or C == B:
        print('No')
    else:
        print('Yes')
elif B == C:
    if A == B or A == C:
        print('No')
    else:
        print('Yes')
elif C == A:
    if B == A or B == C:
        print('No')
    else:
        print('Yes')
else:
    print('No')

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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)
 
typedef pair<int,int> P;
typedef long long ll;
 
const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

int main(){
    int N,Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> A;
    A.push_back(0);

    char now = 'X';
    int num = 0;
    rep(i,N) {
        if (now=='A' && S[i]=='C') {
            num++;
            A.push_back(num);
            now = 'C';
        }
        else {
            now = S[i];
            A.push_back(num);
        }
    }

    rep(i,Q) {
        int l,r;
        cin >> l >> r;
        int ans = A[r]-A[l];
        cout << ans << endl;
    }
}

Measured memory_bytes: 4028
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

int dp[300][300][301];
int n, k;
string s;

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> s >> k;
  n = s.size();
  const int inf = 300;
  for(int i = 0; i < n; i++) for(int p = 0; p <= k; p++) dp[i][i][p] = 1;
  for(int w = 2; w <= n; w++) {
    for(int l = 0; l + w - 1 < n; l++) {
      int r = l + w - 1;
      for(int p = 0; p <= k; p++) {
        dp[l][r][p] = max({
            dp[l+1][r][p],
            dp[l][r-1][p],
            s[l] == s[r] ? dp[l+1][r-1][p] + 2 : -inf,
            p < k ? dp[l+1][r-1][p+1] + 2 : -inf,
            });
      }
    }
  }
  cout << dp[0][n-1][0] << endl;
  return 0;
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF 1e18

#define MAX_N 1000

ll f(ll n){
	if(n<=2)return 0;
	ll next=(n-1)/2;
	return f(next)+1;
}

ll x;

int main(){
	cin.sync_with_stdio(false);
	cin>>x;
	ll lb=0,ub=INF;
	while(ub-lb>1){
		ll mid=(lb+ub)/2;
		if(f(mid)>x)ub=mid;
		else lb=mid;
	}
	cout<<lb<<endl;
	return 0;
}


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

using namespace std;

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define all(n) n.begin(), n.end()

#define FROMTO(var, from, to) for (register int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
#define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
#define FOR(var, to)          UPTO(var, 0, (to)-1)
#define DOWN(var, from)       DOWNTO(var, (from)-1, 0)

#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) cin >> var[i], var[i]--

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)

#define MOD 1000000007
#define INF ((1 << 30)-1)
#define LINF ((1LL << 62)-1)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

struct Comb {
    vector<vector<s64> > data;
    Comb(int n) { // O(n^2)
        data = vector<vector<s64> >(n+1,vector<s64>(n+1,1));
        UPTO(i,1,n) {
            FOR(j,i+1) {
                if (!j || j == i) data[i][j] = 1;
                else data[i][j] = data[i-1][j-1] + data[i-1][j];
            }
        }
    }

    s64 ncr(int n, int r) {
        return data[n][r];
    }
};

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}

int main() {
    string s; cin >> s;
	int n = 1000*(s[5]-'0') + 100 * (s[6]-'0') + 10 * (s[8]-'0') + 1*(s[9]-'0');
	cout << (n<=430 ? "Heisei" : "TBD") << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
//const long double EPS = 1e-14;
const int INF = (1<<30)-1;
//const ll INF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
//template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main () {
  int n;
  cin >> n;
  vi a(n+2);
  rrep(i,n) cin >> a[i];
  int tot = 0;
  rep(i,n+1) {
    tot += abs(a[i] - a[i+1]);
  }

  rrep(i,n) {
    int res = tot - abs(a[i-1]-a[i]) - abs(a[i]-a[i+1]) + abs(a[i-1]-a[i+1]);
    printf("%d\n", res);    
  }
  
  return 0;
}

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

using namespace std;
#define int long long
const int modappl = 1000000007;
int H,W;
string terrain[1000];
int saves[1000][1000];

int nbchems(int lig,int col)
{
    if(lig==H || col == W || terrain[lig][col]=='#')
    {
        return 0;
    }
    if(saves[lig][col]!=-1)
    {
        return saves[lig][col];
    }
    else
    {
        saves[lig][col]=(nbchems(lig+1,col)+nbchems(lig,col+1))%modappl;
        return saves[lig][col];
    }
    
}

signed main()
{
    ios::sync_with_stdio(false);
    cin>>H>>W;
    for(int i = 0 ; i < H ; i ++)
    {
        cin>>terrain[i];
        for(int j = 0 ; j < W ; j ++)
        {
            saves[i][j]=-1;
        }

    }
    saves[H-1][W-1]=1;
    cout<<nbchems(0,0);
}


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

int main() {
  int a[3];
  cin >> a[0] >>a[1]>>a[2];
  if(a[0]==a[1]) cout << a[2];
  if(a[0]==a[2]) cout << a[1];
  if(a[2]==a[1]) cout << a[0];
  
}

Measured memory_bytes: 3660
// ABC79-D      
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define e_b emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ipair;
typedef pair<ll,ll> lpair;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v) //vectorの中身を見る
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
void map_p(map<int,int>& d){cout<<"map: ";for(auto a : d){cout<<"{"<<a.first<<":"<<a.second<<"}";}cout<<endl;} //mapの中身を見る
void set_p(set<int>& d){cout<<"set: ";for(int a : d){cout<<a<<" ";}cout<<endl;} //setの中身を見る


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    
    vector<vector<int>> dp(10,vector<int>(10,0));
    int h,w;
    cin>>h>>w;
    rep(i,10){
        rep(j,10){
            cin>>dp[i][j];
        }
    }
    for(int k=0;k<=9;k++){
        for(int i=0;i<=9;i++){
            for(int j=0;j<=9;j++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
    ll ans=0;
    rep(i,h){
        rep(j,w){
            int now;
            cin>>now;
            if(now==-1) continue;
            ans+=dp[now][1];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  if(s=="SUN")cout<<'7'<<endl;
  if(s=="MON")cout<<'6'<<endl;
  if(s=="TUE")cout<<'5'<<endl;
  if(s=="WED")cout<<'4'<<endl;
  if(s=="THU")cout<<'3'<<endl;
  if(s=="FRI")cout<<'2'<<endl;
  if(s=="SAT")cout<<'1'<<endl;
  return 0;
}

Measured memory_bytes: 256
//abc118_d.cpp
//Sun Jun  2 11:05:01 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	unordered_map<int, int> um{
		{1,2},
		{2,5},
		{3,5},
		{4,4},
		{5,5},
		{6,6},
		{7,3},
		{8,7},
		{9,6},
	};

	int a[m];
	for (int i=0;i<m;i++){
		cin >> a[i];
	}

	sort(a,a+m,greater<>());

	int dp[n+1];
	dp[0] = 0;
	int ketanum[n+1];
	ketanum[0] = 0;

	for (int i=1;i<n+1;i++){
		dp[i] = (-1)*2000000000;
		ketanum[i] = 0;
		for (int j=0;j<m;j++){
			int temp = (-1)*2000000000;
			if (i-um[a[j]]>=0){
				temp = dp[i-um[a[j]]]+1;
			}
			if (dp[i]<temp){
				dp[i] = temp;
				ketanum[i] = a[j];
			}
		}
//		cout << i << " " << dp[i] << " " << ketanum[i] <<  endl;
	}

	int tempn = n;
	while (tempn>0){
		cout << ketanum[tempn];
		tempn = tempn - um[ketanum[tempn]];
	}

	if (tempn != 0){
		cout << "Error?" << endl;
		return 0;
	}
	printf("\n");

//	cout << tempn << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 384
n = int(input())
b = list(map(int, input().split()))
i = 1
ans = []

while i <= len(b):
    test = b[-i]
    if test == len(b)-i+1:
        b.pop(-i)
        ans.append(test)
        i = 1
        continue
    elif i == len(b):
        print(-1)
        exit()
    else:
        i += 1

for i in range(1, n+1):
    print(ans[-i])

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


int main(){
    string s;cin>>s;
    int size=s.size();
    if(size%2==0){
        for(int i=0;i<size;i=i+2){
            cout<<s[i];
        }
        cout<<endl;
    }
    else{
        for(int i=0;i<size+1;i=i+2){
            cout<<s[i];
        }
        cout<<endl;
    }
}

Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=50+2;
char str[maxn];
int main(){
	scanf("%s",str+1);
	int len=strlen(str+1);
	len-=8;
	for (int i=1;i<=len;i++) printf("%c",str[i]);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;

int main(){
    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());

    ll ans = 0;

    for (int i = 0; i < N; i++) {
        ll pre = lower_bound(A.begin(), A.end(), B[i]) - A.begin();
        ll over = C.end() - upper_bound(C.begin(), C.end(), B[i]);
        ans += pre*over;
    }

    cout << ans << endl;

}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fi first
#define sc second
#define ALL(x) x.begin(), x.end()
#define RALL(X) x.begin(), x.end()
#define FOR(i, n, k) for(i=0; i<n; i+=k)
#define FO(i, n, k) for(i=1; i<=n; i+=k)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define N 100005
#define mid ((l+r)/2)
#define dbg(x) (cerr << #x << " : " << x << endl)
#define endl "\n"
#define MOD 100000009

using namespace std;

typedef long long int lli;

int main(){
	ios_base::sync_with_stdio(false);
	string ar[3] = {"Sunny", "Cloudy", "Rainy"};	
	string s;
	cin >> s;
	for(int i=0; i<3; i++){
		if(ar[i] == s){
			cout << ar[(i+1)%3];
		}
	}
	return 0;
}

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

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }
    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }
    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }
    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main(void){
    int n, m;
    cin >> n >> m;
    UnionFind x(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        --a; --b;
        x.merge(a, b);
    }
    ll ans = -1;
    rep(i, n) ans = max(ans, x.size(i));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6416
#include<iostream>
#include<string.h>
using namespace std;

int main()
{
  char s1[1001],s2[1001];
  int ss[1002][1002],u;

  cin>>s1>>s2;

  for(int i=0;i<=strlen(s2)+1;i++)ss[i][0]=i;
  for(int i=1;i<=strlen(s1)+1;i++)ss[0][i]=i;

  for(int i=1;i<=strlen(s2);i++){
    for(int j=1;j<=strlen(s1);j++){
      if(s1[j-1]==s2[i-1]){
	u=min(ss[i-1][j-1],ss[i-1][j]+1);
	ss[i][j]=min(u,ss[i][j-1]+1);
      }
      else{
	u=min(ss[i-1][j-1],ss[i-1][j]);
	ss[i][j]=min(u,ss[i][j-1])+1;
      } 
    }
  }
  cout<<ss[strlen(s2)][strlen(s1)]<<endl;
  return 0;
}

Measured memory_bytes: 5064
#include<bits/stdc++.h>
using namespace std;
int main()
{
	cout<<setprecision(14);
	int t;
	cin>>t;
	double x[t],y[t],res = 0.0;
	int i,j;
	for(i=0;i<t;i++){
		cin>>x[i]>>y[i];
	}
	for(i=0;i<t-1;i++){
		for(j=i+1;j<t;j++){
			res += sqrt(pow(x[i]-x[j],2)+ pow(y[i]-y[j],2))*2/t;
		}
	}
	cout<<res<<'\n';
}


Measured memory_bytes: 256
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.node = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def same(self, x, y):
        return bool(self.root(x) == self.root(y))

    def root(self, x):
        if self.node[x] == x:
            return x
        else:
            self.node[x] = self.root(self.node[x])
            return self.node[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return  # 結合不要
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.node[y] = x
        self.size[x] += self.size[y]

    def return_size(self, x):
        return self.size[self.root(x)]


s = IS()
stack = []
for input_key in s:
    if input_key == '0':
        stack.append('0')
    elif input_key == '1':
        stack.append('1')
    else:  # input_key == 'B'
        if len(stack) > 0:
            stack.pop()
print(''.join(stack))


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

using namespace std;
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<n; i++)


int main() {
    int A,B ;
    cin >> A >> B;

    string S;
    cin >> S;
    if (! (count(S.begin(),S.end(), '-') == 1) || !(S[A] ==  '-') ){
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){

    int i,n,m,sum;
    cin>>n>>m;
    int a[m];
    sum=0;
    for(i=0;i<m;i++){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum==n){
        cout<<"0"<<endl;
    }
    else if(sum<n){
        cout<<n-sum;
    }
    else{
        cout<<"-1"<<endl;
    }

}



Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long int lli;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    lli k,a,b;
    cin>>k>>a>>b;
    lli i;
    for(i=a;i<=b;i++)
    {
        if(i%k==0)
        {
            cout<<"OK";
            return 0;
        }
    }
    cout<<"NG";
    return 0;
}

Measured memory_bytes: 3648
n = int(input())
a = list(map(int,input().split()))

if n%2==0:
    if sorted(a) != [(k//2)*2+1 for k in range(n)]:
        print(0)
    else:
        ans = 2**(n//2)
        print(ans % (10**9+7))
else:
    if sorted(a)!= [0]+[(k//2+1)*2 for k in range(n-1)]:
        print(0)
    else:
        ans = 2**(n//2)
        print(ans % (10**9+7))

Measured memory_bytes: 14008
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
 
int main() {

    int n;
    cin >> n;

    while(1) {
        if(n<=0) {
            cout<<abs(n)<<endl;
            return 0;
        }
        n-=1000;
    }
    

 return 0;
}

Measured memory_bytes: 3628