akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<string> s(n);
	for (int i = 0;i < n;i++) {
		cin >> s[i];
	}
	int ac = 0, wa = 0, tle = 0, re = 0;

	for (int i = 0;i < n;i++) {
		if (s[i] == "AC")ac++;
		else if (s[i] == "WA")wa++;
		else if (s[i] == "TLE")tle++;
		else re++;
	}

	cout << "AC x " << ac << endl;
	cout << "WA x " << wa << endl;
	cout << "TLE x " << tle  << endl;
	cout << "RE x " << re << endl;
	return 0;
}

Measured memory_bytes: 6420
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy
x = int(input())

cnt = x // 11

if x % 11 == 0:
    print(cnt * 2)
elif cnt * 11 + 6 >= x:
    print(cnt * 2 + 1)
else:
    print(cnt * 2 + 2)

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200100;
const ll mod = 1e9 + 7;
ll arr[maxn], n;

int main() {
	cin>>n;
	ll pow4 = 1LL;
	for(int i=1;i<=n;i++) {
		cin>>arr[i];
		if(i < n) {
			pow4 *= 4LL;
			pow4 %= mod;
		}
	}

	sort(arr+1, arr+n+1);
	reverse(arr+1, arr+n+1);

	ll sum = 0LL;
	for(int i=1;i<=n;i++) {
		sum += ((1LL * arr[i] * (i+1))%mod);
		sum %= mod;
	}

	ll result = pow4 * sum;
	cout<<result % mod;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef pair<int,int> P;
typedef long long ll;

int main(void){
    int n;
    cin>>n;
    vector<int>v(n),c(n);
    int ans=0,x=0,y=0;
    for(int i=0;i<n;i++)cin>>v[i];
    for(int i=0;i<n;i++)cin>>c[i];
    for(int i=0;i<n;i++){
        if(v[i]>c[i]){
            x+=v[i];
            y+=c[i];
        }
    }
    cout<<x-y<<endl;
    return 0;
}

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

template <typename T>
class Board {
 public:
  Board(int h, int w) : w_{w}, h_{h}, s_(h * w) {}

  auto& operator()(int i, int j) noexcept { return s_[w_ * i + j]; }
  const auto& operator()(int i, int j) const noexcept { return s_[w_ * i + j]; }

  auto begin() { return s_.begin(); }
  auto end() { return s_.end(); }

  auto begin() const { return s_.begin(); }
  auto end() const { return s_.end(); }

 private:
  int w_;
  int h_;
  std::vector<T> s_;
};

int main() {
  int h, w;
  std::cin >> h >> w;

  Board<char> s(h, w);
  for (int i = 0; i < h; ++i) {
    std::string si;
    std::cin >> si;
    for (int j = 0; j < w; ++j) s(i, j) = si[j];
  }

  Board<int> l(h, w);
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (s(i, j) == '#')
        l(i, j) = 0;
      else if (j == 0)
        l(i, j) = 1;
      else
        l(i, j) = l(i, j - 1) + 1;
    }
  }

  Board<int> r(h, w);
  for (int i = 0; i < h; ++i) {
    for (int j = w - 1; j >= 0; --j) {
      if (s(i, j) == '#')
        r(i, j) = 0;
      else if (j == w - 1)
        r(i, j) = 1;
      else
        r(i, j) = r(i, j + 1) + 1;
    }
  }

  Board<int> u(h, w);
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (s(i, j) == '#')
        u(i, j) = 0;
      else if (i == 0)
        u(i, j) = 1;
      else
        u(i, j) = u(i - 1, j) + 1;
    }
  }

  Board<int> d(h, w);
  for (int i = h - 1; i >= 0; --i) {
    for (int j = 0; j < w; ++j) {
      if (s(i, j) == '#')
        d(i, j) = 0;
      else if (i == h - 1)
        d(i, j) = 1;
      else
        d(i, j) = d(i + 1, j) + 1;
    }
  }

  Board<int> count(h, w);
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j)
      count(i, j) = l(i, j) + r(i, j) + u(i, j) + d(i, j) - 3;
  }

  const auto it = std::max_element(count.begin(), count.end());
  std::cout << *it << std::endl;
}


Measured memory_bytes: 82304
package main

import "fmt"

func main() {
  var X, N int
  fmt.Scanf("%d %d\n", &X, &N)
  arr := make([]int, N)
  var isX int = 0
  for i := 0; i < N; i++ {
    fmt.Scanf("%d", &arr[i])
    if arr[i] == X {
      isX = 1
    }
  }
  if isX == 0 {
    fmt.Println(X)
    return
  }
  
  for i := 0; ; i++ {
    var f int = 0
    for j := 0; j < N; j++ {
      if arr[j] == X-i {
        f = 1
      }
      if f == 1 {
        break
      }
    }
    if f == 0 {
      fmt.Println(X-i)
      return
    }
    f = 0
    for j := 0; j < N; j++ {
      if arr[j] == X+i {
        f = 1
      }
      if f == 1 {
        break
      }
    }
    if f == 0 {
      fmt.Println(X+i)
      return
    }
  }
}

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

int main(){
    vector<int> lst(3,0);
    rep(i,3)cin>>lst[i];
    sort(lst.begin(),lst.end());
    bool flg = 0;
    if(lst[0] == lst[1]){
        if(lst[1] != lst[2])flg = 1;
    }else if(lst[1] == lst[2])flg = 1;

    if(flg == 1){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

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

int main() {
  int N;
  cin >>N;
  bool asd = false;
    
  for(int i=1;i < 10;i++){
    for(int j=1;j < 10;j++){
      if(N == i*j){
        asd = true;
      }
    }
  }
  
  if(asd)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
    
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define MAX 2000

int main(){
    int N, x, y, D[MAX], i, j, d, d1, d2;
    cin >> N >> x >> y;
    for(i=1; i<=N; i++) D[i]=0;
    for(i=1; i<N; i++){
        for(j=i+1; j<=N; j++){
            d1 = j - i;
            d2 = abs(y-j) + abs(x-i) + 1;
            d = min(d1, d2);
            D[d]++;
        }
    }
    for(i=1; i<N; i++) cout << D[i] << endl;

}


Measured memory_bytes: 256
import java.util.Scanner

object Main {
  def main(args: Array[String]) {
    val result = solve(new Scanner(System.in))
    if (result.length > 0) println(result)
  }

  def solve(in: String): String = solve(new Scanner(in))

  def solve(sc: Scanner): String = {
    val s = sc.next.toCharArray

    "%c%d%c".format(s(0), s.length - 2, s.last)
  }
}


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


int main(){
    int N;
    int a[104];
    int sum;
    int Ans=810114514;
    int Ma=-810114514;
    int ma=810114514;
    cin>> N;
    REP(i,N){
        cin >> a[i];
        Ma=max(Ma,a[i]);
        ma=min(ma,a[i]);
    }
    for(int i=ma;i<=Ma;i++){
        sum=0;
        REP(j,N){
            sum+=(i-a[j])*(i-a[j]);
        }
        Ans=min(Ans,sum);
    }
    cout << Ans << endl;
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

q=deque()   #（攻撃が無効となる座標、攻撃によるポイント）
ans=0
cnt=0

attack_point=0
for x,h in XH:
    while q:
        if x<q[0][0]:break  #無効となる攻撃がない場合はwhileを終了
        end_x,end_point=q.popleft()
        attack_point-=end_point #攻撃が無効となる座標<=現在の座標があれば、その攻撃のポイントを引く

    if h<=attack_point: #モンスターの体力よりも攻撃で減らせるポイントの方が大きければ新規攻撃は不要
        pass
    else:   #新規攻撃が必要な場合
        if h%A==0:
            cnt=(h-attack_point)/A  #モンスターの大量をゼロ以下にするために何回攻撃が必要か
        else:
            cnt=(h-attack_point)/A+1
        attack_point+=cnt*A
        q.append((x+2*D+1,cnt*A))   #（攻撃が無効となる座標、攻撃によるポイント）をキューに入れる
        ans+=cnt

print ans

Measured memory_bytes: 53916
n= int(input())
test = [[]for _ in range(n)]
for i in range(n):
    num = int(input())
    for j in range(num):
     a, b= map(int,input().split())
     test[i].append([a-1,b])
ans = 0
for i in range(1,2**n):
    flag = 0
    for j in range(n):
        if(i>>j)&1 == 1:
            for x,y in test[j]:
                if(i>>x)&1 !=y:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans,bin(i)[2:].count('1'))
print(ans)



Measured memory_bytes: 74320
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <string>
#include <vector>

#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;

long long GCD(long long a, long long b) {
    if(b == 0)
        return a;
    else
        return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
    long long g = GCD(a, b);
    return a / g * b;
}
int main() {
    int N;
    cin >> N;
    vector<int> A(N + 1);
    vector<int> B(N);
    rep(i, 0, N + 1) { cin >> A[i]; }
    rep(i, 0, N) { cin >> B[i]; }
    long long count = 0;

    rep(i, 0, N) {
        if(A[i] <= B[i]) {
            count += A[i];
            B[i] -= A[i];
            if(A[i + 1] <= B[i]) {
                count += A[i + 1];
                A[i + 1] = 0;
            } else {
                count += B[i];
                A[i + 1] -= B[i];
            }
        } else {
            count += B[i];
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    rep(i,N-1){
        cin >> B[i];
    }
    A[0] = B[0];
    A[N-1] = B[N-2];
    for(int i=1;i<=N-2;i++){
        A[i] = min(B[i-1],B[i]);
    }
    ll ans = 0;
    rep(i,N){
        ans+=A[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main(){
  int n;
  while(cin >>n,n){
    map<int, long long> com;
    vector<int> g;
    com.clear();
    g.clear();
    while(n--){
      int a;
      long long b,c;
      cin >>a>>b>>c;
      if(!com[a]){g.push_back(a);}
      com[a]+=b*c;
    }
    bool f = false;
    for(int i=0; i<g.size(); i++){
      if(com[g[i]]>=1000000){cout <<g[i]<<endl;f = true;}
    }
    if(!f){cout <<"NA"<<endl;}
  }
  return 0;
}

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

int main(){
  ll N,i;
  ll P[10],Q[10];
  ll ord[10];
  bool x;
  cin >> N;
  ll a,b;
  for(i=0;i<=N-1;i++)
    cin >> P[i];
  for(i=0;i<=N-1;i++)
    cin >> Q[i];
  for(i=0;i<=N-1;i++)
    ord[i] = i+1;
  for(a=0;a<=100000000;a++){
    x = true;
    for(i=0;i<=N-1;i++)
      if(ord[i]!=P[i]) x = false;
    next_permutation(ord,ord+N);
    if(x) break;
  }
  for(i=0;i<=N-1;i++)
    ord[i] = i+1;
  for(b=0;b<=100000000;b++){
    x = true;
    for(i=0;i<=N-1;i++)
      if(ord[i]!=Q[i]) x = false;
    next_permutation(ord,ord+N);
    if(x) break; 
  }
  cout << abs(a-b);
}

Measured memory_bytes: 3604
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  int n; cin >> n;
  vector<int> p(1,0);
  rep(i,n){
    int tmp; cin >> tmp;
    p.push_back(tmp);
  }
  
  int cnt = 0;
  bool chk = false;
  for(int i=1; i <= n;i++){
    if(i==p[i] && !chk){
      cnt++; chk = true;
    }else{
      chk = false;
    }
  }
  
  cout << cnt << endl;
  
  return 0;
}

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

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

typedef tuple<int,int,int> Tr;

const int INF = INT_MAX/2 - 1;
const double EPS = 1e-14;
const int dx[6] = {0, 1, 0, -1, 1, -1};
const int dy[6] = {1, 0, -1, 0, 1, -1};

const int NMAX = 230;
int field[NMAX][NMAX];
#define MAP(x, y) field[x + 100][y + 100]

int main() {
  int T, N;
  while (cin >> T >> N and T) {
    FOR(x, -100, 100) FOR(y, -100, 100) {
      MAP(x, y) = INF;
    }
    REP(i, N) {
      int x, y;
      cin >> x >> y;
      MAP(x, y) = -1;
    }

    int sx,sy;
    cin >> sx >> sy;
    priority_queue<Tr,vector<Tr>,greater<Tr>> que;
    que.push(Tr(1,sx,sy));

    while (!que.empty()) {
      int turn, x, y;
      tie(turn, x, y) = que.top(); que.pop();
      if (turn >= MAP(x, y)) continue;
      MAP(x, y) = turn;
      REP(j, 6) {
        const int nx = x + dx[j], ny = y + dy[j];
        if (MAP(nx, ny) >= 0 and turn <= T)
          que.push(Tr(turn + 1, nx, ny));
      }
    }

    int sum = 0;
    FOR(x, -100, 100) FOR(y, -100, 100) {
      if (MAP(x, y) >= 0 and MAP(x, y) < 100) sum++;
    }
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 3288
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
#include <random>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <functional>
#include <random>
#include <time.h>
#include <chrono>
#include <sstream>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
#define SORT(s) sort(s.begin(), s.end());
#define reverse(s) reverse(s.begin(), s.end());
#define P pair<int,int>
#define mp make_pair
#define valid(x,y,h,w) (0<=x&&x<h&&0<=y&&y<w)
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
using namespace std;
int POW(int x, int y) { return int(pow(double(x), double(y))); }
double log(double a, double b) { return log(b) / log(a); }




int main() {
	char a, b, c, d;
	cin >> a >> b >> c >> d;
	int x = (int(a) - 48) * 10 + int(b) - 48;
	int y = (int(c) - 48) * 10 + int(d) - 48;
	bool xIsM = x > 0 && x <= 12;
	bool yIsM = y > 0 && y <= 12;
	if (xIsM && yIsM) {
		cout << "AMBIGUOUS" << endl;
	}
	else if (xIsM) {
		cout << "MMYY" << endl;
	}
	else if (yIsM) {
		cout << "YYMM" << endl;
	}
	else {
		cout << "NA" << endl;
	}
	return 0;
}



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

/*
 *変数
 */
int h,w,H,W;

/*
 *関数
 */
int ctoi(char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}

/*
 *解 
 */
void solve(){
    printf("%d",(H*W)-((W*h)+((H-h)*w)));
}

/*
 *入力 
 */
int main(){
       std::cin.tie(0);
       std::ios::sync_with_stdio(false);
       std::cin>>H>>W>>h>>w;
       solve();
       return 0;
}

Measured memory_bytes: 256
#define rep(i, a, b) for(int i = a; i < (int)(b); i++)
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
template<class T> inline void chmax(T &a, const T &b) {if(a < b) a = b;}
template<class T> inline void chmin(T &a, const T &b) {if(a > b) a = b;}
const long long INF = 1LL<<60;
const long long MOD = (ll)1e9+7;
// const long long MOD = (ll)1e6+3;
const long long MAX = (ll)1e5+10;

int main(void) {
   string S;
   cin>>S;
   ll N = S.size();
   vector<ll> ans(N,0);
   ll nowr = 0;
   ll nowl = 0;
   ll ce_r;
   rep(i,0,N) {
      if (S[i]=='R') nowr++;
      else nowl++;
      if (i==N-1 || S[i] != S[i+1]) {
         if (S[i]=='R') ce_r = i;
         else {
            // cout<<nowr<<" "<<nowl<<" "<<ce_r<<endl;
            ans[ce_r] = (nowr+1)/2+nowl/2;
            ans[ce_r+1] = (nowr)/2+(nowl+1)/2;
            nowl = 0;
            nowr = 0;
         }
      }
   }
   rep(i,0,N) cout<<ans[i]<<" ";
   cout<<endl;

   return 0;
}

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

int main() {
  int n, k, min=0, sum=0;
  cin >> n >> k;

  for (int i=0; i<n; i++) {
    int t;
    cin >> t;
    if (t<k-t) sum+=t*2;
    else sum+=(k-t)*2;
  }

  cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define maxn 500010
using namespace std;
char s[maxn];
int n;
int place[maxn],dp[maxn];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='0')
			place[i]=i;
		else
			place[i]=place[i-1];
	}
	for(int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1];
		if(s[i]=='1')
		{
			if(s[i-1]=='0'&&s[i-2]=='1')
			{
				dp[i]=max(dp[i],dp[place[i-2]]+(i-2)-place[i-2]);
				dp[i]=max(dp[i],dp[place[i-2]+1]+(i-2)-place[i-2]-1);
			}
			else if(place[i]>1&&s[place[i]-1]=='1')
				dp[i]=max(dp[i],dp[place[i]-2]+i-place[i]);
		}
	}
	printf("%d\n", dp[n]);
	return 0;
}

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

using namespace std;

#define all(v) (v).begin(), (v).end()

using li = long long;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    li K;
    cin >> K;
    
    li K_round_up = ((K + 49) / 50) * 50;
    
    vector<li> seq;
    for (int i = 0; i < 50; i++)
        seq.push_back(49 + K_round_up / 50);
    
    li rest = K_round_up - K;
    for (int i = 0; i < rest; i++)
    {
        int j = max_element(all(seq)) - seq.begin();
        
        for (int k = 0; k < 50; k++)
            if (k == j)
                seq[k] -= 50;
            else
                seq[k]++;
    }
    
    cout << "50\n";
    for (int i = 0; i < 50; i++)
        cout << seq[i] << " ";
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;
  if(a == 0) cout << "1" << endl;
  else if(b == 0) cout << "2" << endl;
  else if(c == 0) cout << "3" << endl;
  else if(d == 0) cout << "4" << endl;
  else if(e == 0) cout << "5" << endl;
}

Measured memory_bytes: 3560
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] treat = new int[n];
        for(int i = 0; i < k; i++){
            int n2 = sc.nextInt();
            for(int j = 0; j < n2; j++){
                treat[sc.nextInt()-1]++;
            }
        }
        int ans = 0;
        for(int t : treat){
            if(t == 0) ans++;
        }
        System.out.println(ans);
    }
}


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

int main(){
	double L;
	cin >> L;
	double x, y, z;
	x = L / 3;
	y = L / 3;
	z = L - 2*x;
	printf("%.10lf\n",x*y*z);
	return 0;
}



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

bool is_prime(int x) {
  if (x <= 1) return false;
  for (int i = 2; i*i <= x; i++) {
    if (x % i == 0) return false;
  }
  return true;
}

int main() {
  int x; cin >> x;
  int p = x;
  while(!is_prime(p)) p++;
  cout << p << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
int main() {
    ll n,m;
    cin >> n >> m;
    vector<int> a(m),b(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
        a[i]--,b[i]--;
    }
    UnionFind uf(n);
    vector<ll> ans;
    ll tmp = n*(n-1)/2;
    for (int i = 0; i < m; ++i) {
        ans.push_back(tmp);
        if(uf.issame(a[m-1-i],b[m-1-i])) continue;

        tmp -= uf.size(a[m-1-i])*uf.size(b[m-1-i]);
        uf.merge(a[m-1-i],b[m-1-i]);
    }
    for (int i = ans.size()-1; i >= 0; --i) {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 3444
//    .------------------------------------------------------------.
//    |   _  __   ___    ___    ___   _  _    ___     _     _  _   |
//    |  | |/ /  / _ \  |   \  |_ _| | \| |  / __|   /_\   | \| |  |
//    |  | ' <  | (_) | | |) |  | |  | .` | | (_ |  / _ \  | .` |  |
//    |  |_|\_\  \___/  |___/  |___| |_|\_|  \___| /_/ \_\ |_|\_|  |
//    |             ___    ___     _     _  _    ___               |
//    |            / _ \  | _ \   /_\   | \| |  / __|              |
//    |           | (_) | |   /  / _ \  | .` | | (_ |              |
//    |            \___/  |_|_\ /_/ \_\ |_|\_|  \___|              |
//    |                 ___   ___    ___    ___                    |
//    |                | _ ) | __|  / __|  / _ \                   |
//    |                | _ \ | _|  | (_ | | (_) |                  |
//    |                |___/ |___|  \___|  \___/                   |
//    |                                                            |
//    |------------------------------------------------------------|
//    |                      .------------.                        |
//    |                      | KerakTelor |                        |
//    |                      |------------|                        |
//    |                      | 2019-10-08 |                        |
//    |                      '------------'                        |
//    '------------------------------------------------------------'

#include <bits/stdc++.h>

#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("tune=native")

#define vec vector
#define prq priority_queue
#define fi first
#define se second

using namespace std;

using ll=long long;
using ld=long double;

//    .-----------------------------------------.
//    |        ___   _   _    ___   ___         | 
//    |       | _ ) | | | |  / __| / __|        | 
//    |       | _ \ | |_| | | (_ | \__ \        | 
//    |       |___/  \___/   \___| |___/        | 
//    |  ___   ___    ___    ___    _  _   ___  | 
//    | | _ ) | __|  / __|  / _ \  | \| | | __| |
//    | | _ \ | _|  | (_ | | (_) | | .` | | _|  | 
//    | |___/ |___|  \___|  \___/  |_|\_| |___| |
//    |                                         | 
//    '-----------------------------------------'

int main()
{
    int n,w;
    scanf("%d%d",&n,&w);
    const int m=1e5;
    const ll inf=1e18;
    vec<ll> dp(m+1,inf);
    dp[0]=0;
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        for(int i=m;i>=b;--i)
            dp[i]=min(dp[i],dp[i-b]+a);
    }
    int res=0;
    for(int i=1;i<=m;++i)
        if(dp[i]<=w)
            res=i;
    printf("%d\n",res);
}



Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e12;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

vector<vector<int>> dp;

// int check(int num){
	// int con = 0;
	// bool flag = true;
	// string n = to_string(num);
	
	// for(int i = 0; i + 1< n.size(); i++){
		// if(i == 0 && n.size() >= 2) {
			// for(int j = 1; j < 10; j++){
				// con += dp[n.size() - i - 1 - 1][j];
			// }
		// } 
		
		// if(i){
			// con += dp[n.size() - i - 1][0];
		// }
		
		/// if(i && abs(n[i] - n[i-1]) >= 1) flag = false;
		
		//// if(flag == false) continue;
		
		
		// for(int j = 1; j < n[i] - '0'; j++){
			// con += dp[n.size() - i - 1][j];
		// }
		
		
	// }
	
	
	
	// return con;
// }

int Stoi(string& num){
	int res = 0;
	
	for(int i = 0; i < num.size(); i++){
		res = res * 10 + num[i] - '0';
	}
	return res;
}

int next(int num){
	string n = to_string(num);
	int z = -1;
	
	for(int i = n.size()-1; i >= 0; i--){
		if(i == 0) {
			if(n[i] - '0' == 9) {
				// z = i-1;
			} else {
				// cout<<"gffd = "<<i<<endl;
				z = i+2;
				n[i]++;
				if(i+1 < n.size()) n[i+1] = max(n[i]-'0'-1ll,0ll)+'0';
				break;
			}
		} else {
			if(n[i-1] + 1 == n[i] || n[i] - '0' == 9) {
				// z = i-1;
			} else { 
			// cout<<"cxzz = "<<i<<endl;
				z = i+2;
				n[i]++;
				if(i+1 < n.size()) n[i+1] = max(n[i]-'0'-1ll,0ll)+'0';
				
				break;
			}
		}
	}
	// cout<<"z = "<<z<<" "<<n<<endl;
	if(z == -2) {
		return Stoi(n);
	}
	
	if(z == -1) {
		n = "1" + n;
		z = 1;
	} 
	
	
	// cout<<"n = "<<n<<endl;
	// cout<<"z = "<<z<<endl;
	for(int i = z; i < n.size(); i++){
		// cout<<"xi = "<<i<<endl;
		n[i] = max(n[i-1] - '0' - 1ll, 0ll) + '0';
	}
	// cout<<"n = "<<n<<endl;
	return Stoi(n);
}

signed main(){
	cout<<fixed<<setprecision(10);
	
	int K;
	int ans = 1;
	
	cin>>K;
	
	for(int i = 1; i < K; i++){
		// cout<<"i = "<<i<<" "<<ans<<endl;
		ans = next(ans);
	}
	
	cout<<ans<<endl;
	
	// dp.resize(14, vector<int>(10));
	
	// for(int i = 1; i < dp[i].size(); i++){
		// dp[0][i] = 1;
	// }
	
	// for(int i = 1; i < dp.size(); i++){
		// for(int j = 0; j < dp[i].size(); j++){
			// for(int k = j - 1; k <= j + 1; k++){
				// if(k < 0 || k >= 10) continue;
				// dp[i][j] += dp[i-1][k];
			// }
		// }
	// }
	
	// for(int i = 1; i < dp.size(); i++){
		// dp[i][0] = 0;
		// for(int j = 1; j < dp[i].size(); j++){
			// dp[i][0] += dp[i-1][j];
		// }
	// }
	
	// for(int i = 1; i <= 23; i++ ){
		// cout<<"i = "<<i<<" "<<check(i)<<endl;
	// }
	
	// int l = 0, h = INF, m = 0;
	
	// while(l+1<h){
		// m = (l+h)>>1;
		
		// if(check(m) <= K) {
			// l = m;
		// } else {
			// h = m;
		// }
	// } 
	
	// cout<<l<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

int v[5];

int main(void) {
    for(int i = 0; i < 5; i++) {
        cin >> v[i];
    }

    sort(v, v + 5);
    reverse(v, v + 5);

    printf("%d %d %d %d %d\n", v[0], v[1], v[2], v[3], v[4]);

    return 0;
}

Measured memory_bytes: 0
n, m, l = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
B = [list(map(int, input().split())) for i in range(m)]
C = [[0 for i in range(l)] for j in range(n)]
for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k]*B[k][j]
for i in range(n):
    print(" ".join(map(str, C[i])))


Measured memory_bytes: 6892
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
	int w=0,f=1;
	char c=' ';
	while(c<'0'||c>'9')c=getchar(),f=c=='-'?-1:f;
	while(c>='0'&&c<='9')w=w*10+c-48,c=getchar();
	return w*f;
}
const int N=1000009;
int n,dp[N][4];
const int mod=1000000007;
signed main(){
	n=read();
	dp[1][1]=dp[1][2]=1;
	dp[1][0]=8;
	for(int i=2;i<=n;++i) {
		for(int j=0;j<=9;++j) {
			for(int k=0;k<4;++k) {
				int t=k;
				if(j==0)t|=1;
				if(j==9)t|=2;
				(dp[i][t]+=dp[i-1][k])%=mod;
			}
		}
	}
	printf("%lld\n",dp[n][3]);
	return 0;
}

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

int main() {
  int n;
    cin >> n;
  int a;
    cin >> a;
  if((n - a) % 500 == 0)
  {
    cout << "Yes" << endl;
  }
  else if(n - a <= 0)
  {
    cout << "Yes" << endl;
  }
  else if(n % 500 - a <= 0)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}
  

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

long gcd(long a, long b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
  
int main() {
  long a,b;
  cin >> a >> b;
  
  long d = gcd(a,b);
  
  long aa = a / d;
  
  long long ans = b * aa;
  
  cout << ans << endl;
  
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var items = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            var answer = items[0] + items[1] + items[2] >= 22 ? "bust" : "win";
            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 13268
N = int(input())
L = sorted([int(x) for x in input().split()])

def solve(N, L):
    answer = 0
    for i in range(2, N):
        c = L[i]
        a = 0
        b = i-1
        while a < b:
            if c >= L[a] + L[b]:
                a += 1
            else: # c < a + b
                answer += b - a
                b -= 1
                #print(L[a], L[b], c, (a, b, i))
    return answer

def check(N, L):
    from itertools import combinations

    answer = 0
    for a, b, c in combinations(L, 3):
        if a < b + c and b < a + c and c < a + b:
            #print(a, b, c)
            answer += 1
    return answer

#print(check(N, L))
print(solve(N, L))


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

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

ll comb(int a, int b)
{
  if (b == 0)
    return 1;
  return a * comb(a - 1, b - 1) / b;
}

int main()
{
  int N, A, B;
  cin >> N >> A >> B;
  vector<ll> v(N);
  REP(i, N)
  cin >> v[i];
  sort(ALL(v));
  reverse(ALL(v));
  ll average = 0;
  REP(i, A)
  average += v[i];
  printf("%.6f\n", (1.0 * average) / (1.0 * A));
  ll choose = 0;
  if (v[0] == v[A - 1])
  {
    int cnt = 0;
    REP(i, N)
    {
      if (v[0] == v[i])
        cnt++;
    }
    for (int i = A; i <= B; ++i)
      choose += comb(cnt, i);
  }
  else
  {
    int cnt1 = 0, cnt2 = 0;
    REP(i, N)
    {
      if (v[A - 1] == v[i])
        cnt1++;
    }
    REP(i, A)
    {
      if (v[A - 1] == v[i])
        cnt2++;
    }
    choose = comb(cnt1, cnt2);
  }
  cout << choose << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int a,b;
  scanf("%d %d",&a,&b);
  int c;
  if (b<10){
    c= a*10+b;
  }else if(b<100){
    c=a*100+b;
  }else{
    c=a*1000+b;
  }
  int i;
  for (i=0;i<318;i++){
    if (i*i==c){
      printf("Yes");
      return 0;
    }
  }
  printf("No");
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n, m;
vector<int> x, y;
vector<int> uzx, uzy;
map<int, int> zx, zy;
int cum[5010][5010];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> n >> m;
  x.resize(n);
  y.resize(n);
  uzx.resize(n);
  uzy.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    uzx[i] = x[i];
    uzy[i] = y[i];
  }
  sort(uzx.begin(), uzx.end());
  sort(uzy.begin(), uzy.end());
  uzx.erase(unique(uzx.begin(), uzx.end()), uzx.end());
  uzy.erase(unique(uzy.begin(), uzy.end()), uzy.end());
  for (int i = 0; i < (int)uzx.size(); i++) {
    zx[uzx[i]] = i;
  }
  for (int i = 0; i < (int)uzy.size(); i++) {
    zy[uzy[i]] = i;
  }
  for (int i = 0; i < n; i++) {
    int px = zx[x[i]] + 1;
    int py = zy[y[i]] + 1;
    cum[px][py]++;
  }
  for (int i = 0; i < 5010; i++) {
    for (int j = 0; j < 5010; j++) {
      if (j + 1 < 5010) cum[i][j + 1] += cum[i][j];
      if (i) cum[i][j] += cum[i - 1][j];
    }
  }
  for (int i = 0; i < m; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int ax = (lower_bound(uzx.begin(), uzx.end(), x1) - uzx.begin());
    int ay = (lower_bound(uzy.begin(), uzy.end(), y1) - uzy.begin());
    int bx = (upper_bound(uzx.begin(), uzx.end(), x2) - uzx.begin());
    int by = (upper_bound(uzy.begin(), uzy.end(), y2) - uzy.begin());
    cout << cum[bx][by] - cum[ax][by] - cum[bx][ay] + cum[ax][ay] << endl;
  }

  return 0;
}


Measured memory_bytes: 101596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

using Graph = vector<vector<int>>;

int main(){
	int x; cin >> x;
	ll ans = 0;
	ans += x / 500 * 1000;
	x %= 500;
	ans += x / 5 * 5;
	cout << ans << endl; 
}

Measured memory_bytes: 256
object Main {
  
  import scala.io.StdIn

  def main(args: Array[String]): Unit = {
    val n = StdIn.readInt
    val as = StdIn.readLine.split(" ").map(_.toInt)
    val cs = Array.fill(Math.pow(5.0, 10.0).toInt + 1)(0)
    as.foreach(i => cs(i) += 1)
    var one = 0
    var two = 0
    cs.foreach(c => if (c != 0) { if (c%2 == 1) one += 1 else two += 1 })
    one += two / 2 * 2
    println(one)
  }
}

Measured memory_bytes: 77936
def c():
    n = int(input())
    s = ['']*n
    for i in range(n):
        s[i] = input()
    s.sort()
    count = 1
    for i in range(1, n):
        if s[i - 1] != s[i]:
            count += 1
    print(count)

def b():
    a,b,c,d = map(int, input().split())
    while True:
        c -= b
        if c <= 0:
            print('Yes')
            break
        a -= d
        if a <= 0:
            print('No')
            break

def a():
    s, w = map(int, input().split())
    if w >= s:
        print('unsafe')
    else:
        print('safe')



c()

Measured memory_bytes: 23884
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int x = sc.nextInt();
		
		while(true){
			boolean flag = true;
			for(int j = 2; j < x; j++){
				if(x%j==0){
					flag = false;
					break;
				}
			}
			if(flag){
				System.out.println(x);
				return;
			}
			x++;
		}



	}

}

Measured memory_bytes: 23124
from itertools import*
N,K,Q,*A=map(int,open(0).read().split())
s=sorted
print(min((s(sum((v[:max(0,len(v)-K+1)]for v in(k*s(v)for k,v in groupby(A,lambda a:a>=Y))),[]))[Q-1:]or[1e10])[0]-Y for Y in A))

Measured memory_bytes: 61276
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>    
#define inf 100000000
#define INF 9223372036854775807
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
long long mod=(long long)1e09+7;

int in(void){
    int i;scanf("%d",&i);
    return i;
}
long long llin(void){
    long long i;scanf("%lld",&i);
    return i;
}
double din(void){
    double i;scanf("%lf",&i);
    return i;
}
void chin(char s[]){
    scanf("%s",s);
}
void print(int a){
    printf("%d\n",a);
}
void llprint(long long a){
    printf("%lld\n",a);
}
void dprint(double a){
    printf("%.10f\n",a);
}
void print2(int a,int b){
    printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
    return a>b?a:b;
}
long long min(long long a,long long b){
    return a<b?a:b;
}
int cmp(const void *a,const void *b){
    return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
    return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
    return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
    return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
    int t=*a;
    *a=*b;
    *b=t;
}
long long gcd(long long x,long long y){
    return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
    return x/gcd(x,y)*y;
}

// write codes below this
// when you use 'sort',
// make sure TYPE macro is correct

int main(void){
    int n,a[1000],ans,i,j;
    while(1){
        n=in();
        if(!n)break;
        rep(i,n)a[i]=in();
        ans=1000000;
        rep(i,n){
            for(j=i+1;j<n;j++){
                ans=min(ans,abs(a[i]-a[j]));
            }
        }
        print(ans);
    }
    return 0;
}



Measured memory_bytes: 2028
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
from itertools import accumulate
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


H, N = zz()
A, B = [], []
for i in range(N):
    a, b = zz()
    A.append(a)
    B.append(b)
# B, A = zip(*sorted(zip(B, A)))

max_a = max(A)
dp = [[100000000]*(H + max_a + 1)] * (N+1)  # dp[i][j]: 魔法i種類で、HPをj減らすのに必要な魔力
#  初期化
for j in range(H):
    if (j % A[0] == 0):
        dp[0][j] = (j//A[0])*B[0]
    else:
        dp[0][j] = (j//A[0]+1)*B[0]
# print(dp)
# print()

for j in range(1, H + max_a + 1):
    for i in range(0, N):

        if(j < A[i]):
            dp[i][j] = min(dp[i-1][j], B[i])
        else:
            # if (j > 8):
            #     print(dp[i - 1][j],
            #           dp[i][j - A[i]] + B[i],
            #           dp[i-1][j-A[i]] + B[i])

            dp[i][j] = min(dp[i - 1][j],
                           dp[i][j - A[i]] + B[i],
                           dp[i-1][j-A[i]] + B[i])


# print(dp)
print(dp[N-1][H])


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

int main(){
    int n;
    cin >> n;
    
    ll T=1, A=1;
    rep(i, n){
        ll t, a;
        cin >> t >> a;
        ll m = max((T-1)/t, (A-1)/a)+1;
        T = m*t;
        A = m*a;
    }

    cout << T+A << endl;
    // printf("%d\n", N);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
ll cur(ll n){
	ll ret = 1;
	while((ret + 1) * (ret + 2) / 2 <= n){
		ret++;
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll z,ret = 0; cin>>z;
	for(ll pre = z, last = 2; last * last <= pre; last++){
		if(z % last == 0){
			ll num = 0; 
			while(z % last == 0){
				z /= last;
				num++;
			}
			ret += cur(num);
		}
	}
	cout<<(z == 1 ? ret : ret + 1);
}

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

int main(void){
    int N, W;
    std::cin >> N >> W;
    std::vector<long long> dp(W + 1, 0);
    for(int i = 0; i < N; i++){
        long long w, v;
        std::cin >> w >> v;
        for(long long j = W - w; j >= 0; j--){
            dp[j + w] = std::max(dp[j + w], dp[j] + v);
        }
    }
    long long ans = 0;
    for(int i = 0; i <= W; i++) ans = std::max(ans, dp[i]);
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 1024
// C - Streamline

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int X[100000];
int d[100000];

int main() {
	int N, M;
	cin >> N >> M;

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

	sort(X, X+M);

	for (int i=0; i<M-1; i++) {
		d[i] = X[i+1] - X[i];
	}

	sort(d, d+M-1);

	ll ans = 0;
	for (int i=0; i<M-N; i++) {
		ans += d[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4260
# coding: utf-8
count = 0
K, S = map(int, input().split())

for x in range(K + 1):
    for y in range(K + 1):
        # print('(x,y,z) = ({},{},?)'.format(x, y))
        if -K <= (x + y - S) <= 0:
            count += 1
print(count)


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define INF 1'000'000

int main() {
    i64 N; cin >> N;
    vector<i64> A(N);

    i64 maxi;
    i64 maxabs = 0;
    REP(i, N) {
        cin >> A[i];
        if (chmax(maxabs, abs(A[i]))) maxi = i;
    }

    bool ok = true;
    REP(i, N - 1) {
        if (A[i] > A[i + 1]) {
            ok = false;
            break;
        }
    }
    if (ok) {
        cout << 0 << endl;
        return 0;
    }

    using P = pair<i64, i64>;
    vector<P> ops;

    REP(i, N) {
        if (maxi != i) {
            A[i] += A[maxi];
            ops.emplace_back(maxi, i);
        }
    }

    if (A[maxi] >= 0) {
        REP(i, N - 1) {
            A[i + 1] += A[i];
            ops.emplace_back(i, i + 1);
        }
    } else {
        for (i64 i = N - 1; i > 0; i--) {
            A[i - 1] += A[i];
            ops.emplace_back(i, i - 1);
        }
    }

    assert(ops.size() <= 2 * N);
    cout << ops.size() << endl;

    REP(i, ops.size()) {
        i64 x = ops[i].first + 1;
        i64 y = ops[i].second + 1;
        cout << x << " " << y << endl;
    }

    return 0;
}

Measured memory_bytes: 256
N,K = map(int,input().split(" "))
A = list(map(int,input().split(" ")))

def gcd(n,m):
    while n:
        a = n
        n = m % n
        m = a
    return m

def main():
    if K > max(A):
        return 0
    i = A[0]
    for a in A:
        i = gcd(i,a)
    return not(K%i)

print(['IMPOSSIBLE','POSSIBLE'][main()])

Measured memory_bytes: 14252
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const double PI=acos(-1);

int main(){
    ll n, m;
    cin >> n >> m;
    vector<ll> l(m), l2(m-1);
    rep(i, m) cin >> l[i];
    sort(l.begin(), l.end());
    rep(i, m-1) l2[i] = l[i+1] - l[i];
    sort(l2.rbegin(), l2.rend());
    ll sum = 0;
    rep(i, m-1){
        if(i < n-1) continue;
        sum += l2[i];
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
 
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define int long long int
#define fi first
#define se second
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
#define pow10(n) stoll("1"+string(n,'0'))
//fill(all(arr),1)
//if(map.count(key)){}
//bitset<20>(n);
//int mini=min({a,b,c,d,e});
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;

int32_t main(){
  FIO
  string s;
  cin>>s;
  if(s[1]=='B')cout<<"ARC";
  else cout<<"ABC";
  
  return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <utility>

#define INF 1000000005


using namespace std;

long long n, size;
pair <long long, long long> tab[100000];
long long dp[1000000];
long long minimum = INF;
long long score = 0;

int main(){
    
    for(int i = 1 ; i < 1000000; i++){
        dp[i] = INF;
    }
    cin >> n >> size;
    
    
    for(int i = 0; i < n; i++){
        cin >> tab[i].first >> tab[i].second;
        // first - weight
        // second - value
    }
    
    long long maxValue = 0;
    
    for(int element = 0; element < n; element++){
        for(int i = maxValue; i >= 0; i--){
            
            dp[i + tab[element].second] = min(dp[i + tab[element].second], dp[i] + tab[element].first);
            //cout << dp[i + tab[element].second] << " ";
            maxValue = max(maxValue, i + tab[element].second);
            
        }
        
    }
   // cout<<maxValue;
    /*
    for(int i = 0; i < 10; i++){
        cout << dp[i] << " ";
    }*/
    
    //cout << dp[140] << endl;
    
    for(int i = maxValue; i >= 0; i--){
        //cout << i << " ";
        if(dp[i] <= size){
            //cout<< dp[i] << "<" << size << "\n";
            cout << i;
            return 0 ;
        }
    }
    //cout<<"ala";
}


Measured memory_bytes: 8448
h, w, k = list(map(int, input().split()))

choco = [list(map(int, list(input()))) for i in range(h)]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_yoko = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_yoko
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_yoko + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1)):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        # print(iw, count_white)

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_yoko + 1)
                # print('iw: ', iw, 'last: ', w_last_cut_pos)

            else:
                # 1つしか動かしてないのに、Kマスを超えてしまった場合は、この横の切り方では達成不可能なので次のh_cutに
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    # print(num_cut)

print(ans)


Measured memory_bytes: 9312