akhauriyash/Code-Regression huggingface dataset:
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


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


ll LCM(ll a,ll b){
  return a/GCD(a,b)*b;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}




ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}

vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll p=2;p<=sqrt(n);p++){
    if(n%p!=0) continue;
    ll cnt=0;
    while(n%p==0){
      n/=p;
      cnt++;
    }
    ans.push_back(make_pair(p,cnt));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll H,W,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
  cin>>H>>W;
  vector<string> v(H);
  vector<vector<ll>> w(H,vector<ll>(W,-1));
  rep(i,H) cin>>v[i];
  queue<pint> que;
  rep(i,H) rep(j,W) if(v[i][j]=='#') w[i][j]=0,que.push(pint(i,j));
  while(!que.empty()){
    auto c=que.front();que.pop();
    rep(i,4){
      ll nx=c.second+dx[i];
      ll ny=c.first+dy[i];
      if(nx<0 || W<=nx || ny<0 || H<=ny) continue;
      if(w[ny][nx]==-1) w[ny][nx]=w[c.first][c.second]+1,que.push(pint(ny,nx));
    }
  }
  ll ans=0;
  rep(i,H) rep(j,W) chmax(ans,w[i][j]);
  cout<<ans<<endl;
}

Measured memory_bytes: 25524
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
using P=pair<long long,long long>;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
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; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}
ll modpow(ll a,ll n){
  if(n==0)return 1;
  if(n%2==0){
    ll t=modpow(a,n/2);
    return t*t%MOD;
  }
  return a*modpow(a,n-1)%MOD;
}
ll modinv(ll a){
  return modpow(a,MOD-2);
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  int n;
  cin >> n;
  vector<ll>a(n);
  map<ll,ll>mp;
  rep(i,n){
    cin >> a[i];
    auto pf=prime_factorize(a[i]);
    for(auto p:pf){
      mp[p.first]=max(p.second,mp[p.first]);
    }
  }
  ll lcm=1;
  for(auto p:mp){
    lcm*=modpow(p.first,p.second);
    lcm%=MOD;
  }
  ll ans=0;
  rep(i,n){
    ans+=lcm*modinv(a[i]);
    ans%=MOD;
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 1024
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;
#define rep(i,n) for (int i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define ll long long
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>


string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 
 

#define MAXN  100010
int sentakushi[MAXN] = {};
int num_friends[MAXN] = {};
int called[MAXN] = {};
vector<int> tree[MAXN];
int N;
int K;

void calc(int ni){
    int count=0;
    int ni_f;
    //cout << ni << endl;
    //cout << num_friends[ni] << endl;
    rep(fi,num_friends[ni]){
        ni_f = tree[ni][fi];
        if(called[ni_f] > 0){
            count++;
        }
    }

    rep(fi,num_friends[ni]){
        ni_f = tree[ni][fi];
        if(called[ni_f]==0){
            sentakushi[ni_f] = K - 1 - count;
            count++;
        }
    }
    
    rep(fi,num_friends[ni]){
        ni_f = tree[ni][fi];
        if(called[ni_f]==0){
            called[ni_f] = 1;
            calc(ni_f);
        }
    }

}


int main(){
    cin >> N;
    cin >> K;

    if(N==1) cout << K << endl;
    else{

        int a,b;
        for( int ni = 0 ; ni < N-1 ; ni++ ){
            cin >> a >> b;
            tree[a].push_back(b);
            tree[b].push_back(a);
            num_friends[a]++;
            num_friends[b]++;
        }

        int starti;
        rep(ni,N){
            if(num_friends[ni]==1) starti = ni;
        }

        called[starti] = 1;
        sentakushi[starti] = K;
        calc(starti);

        //cout << "sss" << endl;
        //rep(ni,N+2) cout << sentakushi[ni] << endl;
        //cout << "ss" << endl;
        ll ans=1;
        for(int ni = 1 ; ni <=N ; ni++) ans = ( ans * sentakushi[ni] ) % MOD;
        cout << ans << endl;
    }
}

Measured memory_bytes: 11520
#include<bits/stdc++.h>
using namespace std;
int n,m,a[50],b[50],A[51],B[51];
int dp[51][51][51][51][2][2];
int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(a[i]==-1)a[i]=0;
    A[i+1]=A[i]+a[i];
  }
  for(int i=0;i<m;i++){
    cin>>b[i];
    if(b[i]==-1)b[i]=0;
    B[i+1]=B[i]+b[i];
  }
  for(int x=n;x>=0;x--)
    for(int y=m;y>=0;y--)
      for(int s=x;s>=0;s--)
        for(int t=y;t>=0;t--)
          for(int f=1;f>=0;f--)
            for(int p=1;p>=0;p--){
              int &res=dp[x][y][s][t][f][p];
              if(p==0){
                res=-1e9;
                if(f==1&&x==s&&y==t)res=max(res,0);
                else res=max(res,dp[x][y][x][y][x==s&&y==t][1]+A[x]-A[s]-B[y]+B[t]);
                if(x<n&&a[x]==0)res=max(res,dp[x+1][y][s][y][0][1]);
                if(x<n&&a[x]>0)res=max(res,dp[x+1][y][s][t][0][1]);
              }else{
                res=1e9;
                if(f==1&&x==s&&y==t)res=min(res,0);
                else res=min(res,dp[x][y][x][y][x==s&&y==t][0]+A[x]-A[s]-B[y]+B[t]);
                if(y<m && b[y]==0)res=min(res,dp[x][y+1][x][t][0][0]);
                if(y<m && b[y]>0)res=min(res,dp[x][y+1][s][t][0][0]);
              }
            }
  cout<<dp[0][0][0][0][0][0]<<endl;
  return 0;
}

Measured memory_bytes: 65852
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    long long solve(long long n) {
        long long res = 1e18;

        for (int i = 1; i * 1LL * i <= n; ++i) {
            if (n % i == 0) {
                long long a = i;
                long long b = n / i;
                res = min(res, a - 1 + b - 1);
            }
        }

        return res;
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    long long n;
    cin >> n;
    Solution sol;
    cout << sol.solve(n) << "\n";

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
    long long int ans,sum=0,N,r=0,g=0,b=0,i,j;
    scanf("%d",&N);
    char S[N];
    scanf("%s",S);
    for(i=0;i<N;i++){
        if(S[i]=='R') r++;
        else if(S[i]=='B') b++;
        else g++;
    }
    ans=r*g*b;
    for(i=0;i<N;i++){
        for(j=1;i+j*2<N;j++){
            if(S[i]!=S[i+j] && S[i+j]!=S[2*j+i] && S[2*j+i]!=S[i]) sum++;
        }
    }
    printf("%lld\n",ans-sum);
    return 0;
}

Measured memory_bytes: 1700
N=int(input())
A=[0]*N
A=list(map(int,input().split()))
money=1000
money_temp=1000
kazu=0
ma=0
mi=float('inf')
stop=0
for i in range(0,N-1):
    money=money+A[i]*kazu
    kazu=0
    if(A[i]<A[i+1]):
        kazu=money//A[i]
        money=money-A[i]*kazu

    elif(A[i+1]<=A[i]):
        pass

money=money+A[N-1]*kazu
print(money)


Measured memory_bytes: 62000
const input = require('fs').readFileSync('/dev/stdin', 'utf8');

const inputs = input.trim().split('\n');
const n = Number(inputs.shift());
const adj = inputs.map((s) => s.split(' ').map(Number));

class Queue {
  constructor() {
    this.list = [];
  }
  isEmpty() {
    return !this.list.length;
  }
  enqueue(item) {
    this.list.push(item);
  }
  dequeue() {
    return this.list.shift()
  }
}

class Node {
  constructor(id) {
    this.id = id;
    this.list = [];
    this.params = new Map();
  }
  add(node) {
    this.list.push(node);
  }
  get(key) {
    return this.params.get(key);
  }
  set(key, value) {
    return this.params.set(key, value);
  }
  has(key) {
    return this.params.has(key);
  }
  toString() {
    return [this.id, this.has('depth') ? this.get('depth') : -1].join(' ');
  }
}

class Graph {
  constructor() {
    this.map = new Map();
    this.queue = new Queue();
  }
  setNode(node) {
    this.map.set(node.id, node);
  }
  hasNode(id) {
    return this.map.has(id);
  }
  getNode(id) {
    return this.map.get(id);
  }
  bfs1() {
    while (!this.queue.isEmpty()) {
      const parent = this.queue.dequeue();
      parent.list.forEach(child => {
        if (child.has('depth')) {
          return;
        }
        child.set('depth', parent.get('depth') + 1);
        this.queue.enqueue(child);
      });
    }
  }
  bfs2(depth, ...nodes) {
    const children = [];
    nodes.forEach(node => {
      if (node.has('depth')) {
        return;
      }
      node.set('depth', depth);
      children.push(...node.list);
    });
    children.length && this.bfs2(depth + 1, ...children);
  }
  print() {
    for (let i = 1; i <= this.map.size; i++) {
      const node = this.map.get(i);
      console.log(node.toString());
    }
  }
}

const graph = new Graph();

adj.forEach(([id, k, ...ck]) => {
  graph.hasNode(id) || graph.setNode(new Node(id));
  const node = graph.getNode(id);
  ck.forEach(c => {
    graph.hasNode(c) || graph.setNode(new Node(c));
    const child = graph.getNode(c);
    node.add(child);
  });
});

const root = graph.getNode(1);
// root.set('depth', 0);
// graph.queue.enqueue(root);
graph.bfs2(0, root);

graph.print();



Measured memory_bytes: 17272
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    a,b=map(int,input().split())
    n=b-a
    print(n*(n-1)//2-a)
resolve()

Measured memory_bytes: 38256
n = int(input())
ans = 0
t = 0
J = 0
for i in range(1,n):
    for j in range(i,n):
        if i*j >= n:break
        if i == j : t+=1
        ans +=1
        J = j
    if i*J >= n:break

print(2*ans -t)


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

#define ll  long long
#define ull unsigned ll
#define LD long double

#define MP make_pair
#define BS binary_search
#define GCD __gcd
#define pb push_back
#define pp pop_back
#define ff first
#define ss second

#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define sz(a) (int)a.size()

int main(){

    int N,K,x;
    cin >> N >> K;
    vector<int> vec;
    for(int i=0;i<N;i++){
        cin >> x;
        vec.push_back(x);
    }
    sort(vec.rbegin(),vec.rend());
    int sum = 0;
    for(int i=0;i<K;i++){
        sum += vec[i];
    }
    cout << sum << endl;
	return 0;
}


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

int main() {
    ll n;
    cin >> n;
    ll a[n + 1];
    rep(i, n + 1) cin >> a[i];

    ll ans = 0;
    rep(i, n) {
        ll b;
        cin >> b;
        ll t = min(b, a[i] + a[i + 1]);
        ans += t;
        a[i + 1] -= t - min(b, a[i]);
    }

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define drep(i,cc,n) for(int i=(cc);i<=(n);++i)
#define rep(i,n) drep(i,0,(n)-1)
#define drrep(i,cc,n) for(int i=(cc);i>=(n);--i)
#define rrep(i,n) drrep(i,0,(n)-1)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,v.size())if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define arrprint(v,n) rep(i,n)if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define matprint(v,n,m) rep(i,n){rep(j,m){cout << v[i][j] << " ";}cout << endl;}
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
using ll = long long;
using P = pair<int,int>;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す

int main(){
    int a,b,c,k;
    cin >> a >> b >> c;
    cin >> k;
    int cnt = 0;
    while(a>=b){
        b*=2;
        cnt++;
    }
    while(b>=c){
        c*=2;
        cnt++;
    }
    string ans;
    if(cnt<=k)ans = "Yes";
    else ans = "No";

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

    return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long int ll;
const int N = 1e5 + 5;
//const int INF = 1e9 + 5;
//int a[N];
void solve_test_case(){
	int n,k,s = 0;
	cin>>n>>k;
	vector<int> price(n);
	for(auto &i :price){
		cin>>i;
	}
	sort(price.begin(), price.end());
	for(int i = 0;i < k;++i){
		s += price[i];
	}
	cout<<s<<"\n";
}
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin>>t;
	for(int i = 0;i < t;++i){
		solve_test_case();
	}
}


Measured memory_bytes: 3660
flag = False
while True:
    A,B = map(int,input().split())
    if A == 0:
        break
    ans = []
    for i in range(A,B + 1):
        if i % 400 == 0 or (i % 100 != 0 and i % 4 == 0):
            ans.append(i)
    if flag:
        print('')
    flag = True
    if len(ans) != 0:
        for i in ans:
            print(i)
    else:
        print('NA')

Measured memory_bytes: 7620
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
using namespace std;

typedef pair<int,int> pi;

const int N=305;
const int MOD=1000000007;

int n,m,f[2][N][N];
vector<pi> vec[N];

void updata(int &x,int y)
{
    x+=y;x-=x>=MOD?MOD:0;
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int l,r,x;scanf("%d%d%d",&l,&r,&x);
        vec[r].pb(mp(l,x));
    }
    int now=0;
    f[0][0][0]=3;
    for (int i=1;i<n;i++)
    {
        for (int j=0;j<=i;j++)
            for (int k=0;k<=j;k++)
            {
                if (!f[now][j][k]) continue;
                for (int l=0;l<vec[i].size();l++)
                {
                    int x=vec[i][l].first,y=vec[i][l].second;
                    if (y==1&&x<=j||y==2&&(x<=k||x>j)||y==3&&x>k) {f[now][j][k]=0;break;}
                }
                if (!f[now][j][k]) continue;
                updata(f[now^1][j][k],f[now][j][k]);
                updata(f[now^1][i][k],f[now][j][k]);
                updata(f[now^1][i][j],f[now][j][k]);
                f[now][j][k]=0;
            }
        now^=1;
    }
    int ans=0;
    for (int i=0;i<=n;i++)
        for (int j=0;j<=i;j++)
        {
            for (int k=0;k<vec[n].size();k++)
            {
                int x=vec[n][k].first,y=vec[n][k].second;
                if (y==1&&x<=i||y==2&&(x<=j||x>i)||y==3&&x>j) {f[now][i][j]=0;break;}
            }
            updata(ans,f[now][i][j]);
        }
    printf("%d",ans);
    return 0;
}

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

using ll = long long;

int main() {
  ll N, K;
  cin >> N >> K;

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

  ll sum = 0;
  ll befSum = 0;
  for (int i = 0; i < N; i++) {
    sum += A[i];
    if (i>=K) {
      sum -= A[i-K];
      if ( sum > befSum) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
    befSum = sum;
  }

  return 0;
}

Measured memory_bytes: 5188
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;

const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main()
{
    string x;
    cin >> x;
    int t = 0,ans = 0;
    for(int i = x.size()-1; i >= 0; i--){
        if(x[i] == 'T') t++;
        else{
            if(t > 0) t--;
            else ans++;
        }
    }
    cout << ans*2 << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;
// Ax = v
// 疎な連立方程式を解く
// Eが辺
// xが最終的な辺の係数

struct edge{
  ll from, to, num;
  edge(ll a, ll b, ll c):from(a), to(b), num(c){}
};
struct graphMatSolver{
  vector<bool> used;
  vector<ll> x, v;
  vector<vector<edge>> G;
  vector<edge> E;
  ll cnt = 0;
  ll N, M;

  graphMatSolver(ll max_n, ll max_m, vll dat){
    N = max_n, M = max_m;
    used.resize(N, false);
    x.resize(M, 0);
    v.resize(N, 0);
    G.resize(N);
    for(int i=0;i<dat.size();i++) v[i] = dat[i];
  }

  void add_edge(ll from, ll to){
    if(from!=to){
      G[from].push_back(edge(from, to, cnt));
      G[to].push_back(edge(from, to, cnt));
      E.push_back(edge(from, to, cnt));
    }
    cnt++;
  }

  ll dfs(ll now){
    ll ret = v[now];
    used[now] = true;
    for(auto e:G[now]){
      ll to = (e.to==now?e.from:e.to);
      if(used[to]) continue;
      ll tmp = dfs(to);
      if(now==e.from) x[e.num] = tmp;
      else x[e.num] = tmp;
      ret ^= tmp;
    }
    return ret;
  }

  ll solve(){
    for(int i=0;i<N;i++){
      if(used[i]) continue;
      ll y = dfs(i);
      if(y!=0) return 0;
    }
    return 1;
  }
  edge & operator [](int k){
    return E[k];
  }
};

int main(int argc, char const *argv[]) {
  ll n, m;std::cin >> n >> m;
  vvl bomb = VV(n, 2, 0, ll);
  vll x(n+1, 0);

  for(int i=0;i<n;i++) {
    scanf("%lld %lld", &bomb[i][0], &bomb[i][1]);
    x[i+1] = bomb[i][0];
  }
  sort(all(bomb));
  sort(all(x));
  vll c(n+1, 0);

  for(int i=0;i<n;i++){
    if(i==n-1&&!bomb[i][1]) continue;
    if((bomb[i][1]&&i==n-1)||(bomb[i][1]!=bomb[i+1][1])) c[i+1] = 1;
  }

  graphMatSolver mg(n+2, m+2, c);
  c[0] = 1;
  graphMatSolver mg2(n+2, m+2, c);

  //何本目から何本目か
  for(int i=0;i<m;i++){
    ll a, b;scanf("%lld %lld", &a, &b);
    ll A = upper_bound(all(x), a-1) - x.begin() - 1;
    ll B = upper_bound(all(x), b) - x.begin() - 1;
    // A以下flip, B以下flip
    mg.add_edge(A, B);
    mg2.add_edge(A, B);
  }
  if(mg.solve()){
    vll ans;
    for(auto e:mg.E) if(mg.x[e.num]) ans.push_back(e.num);
    std::cout << ans.size() << '\n';
    for(int i=0;i<ans.size();i++) std::cout << ans[i] + 1 << (i==ans.size()-1?"\n":" ");
    return 0;
  }

  if(mg2.solve()){
    vll ans;
    for(auto e:mg2.E) if(mg2.x[e.num]) ans.push_back(e.num);
    std::cout << ans.size() << '\n';
    for(int i=0;i<ans.size();i++) std::cout << ans[i] + 1 << (i==ans.size()-1?"\n":" ");
    //std::cout << "debug" << '\n';
    return 0;
  }
  std::cout << -1 << '\n';
  return 0;
}


Measured memory_bytes: 61664
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[n];
		
		int sum = 0;
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			sum += a[i];
		}
		int pop = 0;
		for(int i = 0; i < n; i++) {
			if(!((double)a[i] < (double)sum/(4*(double)m))) {
				pop++;
				if(pop >= m) {
					break;
				}
			}
		}
		if(pop >= m) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}
	
}


Measured memory_bytes: 23124
//https://atcoder.jp/contests/abc069/tasks/arc080_b
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define FOR(i,a,b) for(int64_t i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
int main() {
    ll H, W; cin>>H>>W;
    ll N; cin>>N;
    vector<pair<ll,ll>> an(N);
    REP(i,N){
        ll a; cin>>a;
        an.at(i) = {a,i+1};
    }
    sort(an.begin(),an.end(),[](const auto& a,const auto& b){return a.first > b.first;});
    vector<vector<ll>> ans(H,vector<ll>(W));
    ll p = 0;
    for(auto&& hh :ans){
        for(auto&& ww : hh){
            ww = an.at(p).second;
            an.at(p).first--; //減らす
            if(an.at(p).first <= 0) ++p;
        }
    }
    //1つおきにreverse
    REP(y,ans.size()){
        if(y%2==1) reverse(ans[y].begin(),ans[y].end());
    }
    REP(y,ans.size()){
        REP(x,ans.at(y).size()){
            if(x!=0) cout<<" ";
            cout<<ans[y].at(x);
        }
        cout<<endl;
    }
    return 0;
}

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

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

int main(){
	int n;
	while( cin >> n, n ){
		rep(i,n){
			int m, e, j;
			cin >> m >> e >> j;
			if( m==100 || e==100 || j==100 )
				cout << "A" << endl;
			else if( (m+e)/2 >= 90 )
				cout << "A" << endl;
			else if( (m+e+j)/3 >= 80 )
				cout << "A" << endl;
			else if( (m+e+j)/3 >= 70 )
				cout << "B" << endl;
			else if( (m+e+j)/3 >= 50 && (m>=80 || e>=80) )
				cout << "B" << endl;
			else
				cout << "C" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1156
INF = 10**18

N, M, X = map(int, input().split())
C = [0]*N
A = [[] for i in range(N)]
for i in range(N):
    src = list(map(int, input().split()))
    C[i] = src[0]
    A[i] = src[1:]
ans = INF
for i in range(1<<N):
    point = [0]*M
    m = 0
    for j in range(N):
        if i&(1<<j) > 0:
            m += C[j]
            for ii, a in enumerate(A[j]):
                point[ii] += a
    ok = True
    for j in range(M):
        if point[j] < X:
            ok = False
            break
    if ok:
        ans = min(ans, m)
if ans == INF:
    print(-1)
else:
    print(ans)


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

int gcd(int a, int b){
	if(b == 0){
		return a;
	}
	else{
		return gcd(b, a % b);
	}
}

int main(){
	int K, a, b, c, ans = 0;
	scanf("%d", &K);
	for(a = 1; a <= K; a++){
		for(b = 1; b <= K; b++){
			for(c = 1; c <= K; c++){
				ans += gcd(a, gcd(b, c));
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

int main(){
    int H, N;
    int A[1002], B[1002];
    long long cost_table[10002];

    cin >> H >> N;
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }
    for(int h=1;h<=H;h++){
        cost_table[h] = 1e18;
    }
    for(int h=1;h<=H;h++){
        for(int i=0;i<N;i++){
            if(A[i] >= h){
                cost_table[h] = min(cost_table[h], (long long)B[i]);
            }
            else{
                cost_table[h] = min(cost_table[h], cost_table[h-A[i]] + (long long)B[i]);
            }
        }
    }
    cout << cost_table[H] << endl;
    return 0;
}

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

int main(){
  int N;
  cin>>N;
  vector<int> A(N+1);
  for(int i=1;i<N+1;i++)cin>>A[i];
  
  vector<bool> flag(1000000010);
  
  string ans="YES";
  
  for(int i=1;i<N+1;i++){
    int index=A[i];
    if(flag[index]==true){
      ans="NO";
      break;
    }
    flag[index]=true;
  }
  cout<<ans<<endl;
  
  
}

Measured memory_bytes: 123136
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

S = input()
n = len(S)
dp = [[0]*(13) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
    c = 0
    if S[i]=="?":
        c = -1
    else:
        c = int(S[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki*10+j)%13] += dp[i][ki]
    for j in range(13):
        dp[i+1][j] %= mod

print(dp[n][5])


Measured memory_bytes: 62172
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    Integer[] d = new Integer[n];
    for (int i = 0; i < n; i++){
      d[i] = Integer.parseInt(sc.next());
      // 右辺はint型だがオートボクシングされている
    }
    Arrays.sort(d,(n1,n2) -> {return n2 - n1;});
    int ans = 0, last = 101;
    for (int i = 0; i < n; i ++){
      if (last != d[i]){
        ans += 1;
        last = d[i];
      }
    }
    System.out.println(ans);
    
  }
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N, K;
std::string S;

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

    std::cin >> N >> K >> S;
    
    int zeros = 0, n = 0, mx = 0;

    for(int i=0,j=0,k=0;i<N;){
        while(j < N && zeros <= K){
            if(S[j] == '0'){
                if(zeros == K){
                    break;
                }
                
                zeros += 1;
            }

            while(k < N && S[k] == S[j]){
                n += 1;
                k += 1;
            }

            j = k;
        }

        mx = std::max(mx, n);

        if(S[i] == '0'){
            zeros -= 1;
        }

        int l = i;

        while(l < N && S[l] == S[i]){
            n -= 1;
            l += 1;
        }

        i = l;
    }
    
    std::cout << mx << std::endl;
}


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

ba = []
for i in range(M):
    ba.append([ab[i][1], ab[i][0]])
ba.sort() # sorted on b

ans = 0
t = 0
for i in range(M):
    if t <= ba[i][1]:
        ans += 1
        t = ba[i][0]
print(ans)


Measured memory_bytes: 35040
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define MOD 1000000007
#define PI 3.14159265358979323846
#define INF 1 << 30

using namespace std;
typedef long long ll;
typedef pair<int, int> pp;

int abc[3];

string Sim(vector<string> & s, int &ok) {
	int i, a, b;
	string ans = "";
	rep(i, s.size()) {
		a = abc[s[i][0] - 'A'];
		b = abc[s[i][1] - 'A'];
		if (a == 0 && b == 0) {
			ok = 0;
			return "";
		}
		if (a == 1 && b == 1 && s.size() - 1 > i) {
			int p = s[i + 1].find(s[i][0]);
			if (0 <= p && p < 2) {
				abc[s[i][0] - 'A']++; abc[s[i][1] - 'A']--;
				ans += s[i][0];
			}
			else {
				abc[s[i][0] - 'A']--; abc[s[i][1] - 'A']++;
				ans += s[i][1];
			}
		}
		else if (a <= b) {
			abc[s[i][0] - 'A']++; abc[s[i][1] - 'A']--;
			ans += s[i][0];
		}
		else {
			abc[s[i][0] - 'A']--; abc[s[i][1] - 'A']++;
			ans += s[i][1];
		}
	}
	return ans;
}

int main(void) {
	int num, i, ok = true;
	cin >> num;
	rep(i, 3)
		cin >> abc[i];
	string ans;
	vector<string> s(num);
	rep(i, num)
		cin >> s[i];
	ans = Sim(s, ok);
	if (ok) {
		printf("Yes\n");
		rep(i, num)
			cout << ans[i] << "\n";
	}
	else
		printf("No\n");
	return 0;
}

Measured memory_bytes: 6692
#include <cstdio>
#define ll long long
#define maxn 100000
int f[maxn + 1];
int main() {
    int n, x, nr = 0, rez;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        f[x]++;
    }
    for (int i = 1; i <= maxn; i++)
        if (f[i] > 0)
            nr++;
    if(nr % 2 == 1)
        rez = nr;
    else
        rez = nr - 1;
    printf("%d", rez);
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using in6 = int64_t;
using ind = double;
using pii = pair<int,int>;
using psi = pair<string,int>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define repa(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define repdown(i,n) for(in6 i = n; i > 0; i--)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 2147483647
#define dset(n) cout << fixed << setprecision(n)

void yes() {
  cout << "Yes";
}

void no() {
  cout << "No";
}

int main() {
  kyun;
  in6 n,k;
  cin >> n >> k;
  in6 ans = n % k;
  cout << min(ans,abs(ans-k));
  hinata;
}

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

long dp[55][2525][55];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a; cin >> n >> a;
    int x[50]; for(int i=0; i < n; ++i) cin >> x[i];

    dp[0][0][0] = 1;

    for(int i=0; i < n; ++i) {
        for(int j=0; j <= 2500; ++j) {
            for(int k=0; k <= n; ++k) {
                dp[i+1][j][k] += dp[i][j][k];
                if(k > 0 && j >= x[i]) dp[i+1][j][k] += dp[i][j-x[i]][k-1];
            }
        }
    }

    long ans = 0;
    for(int k=1; k <= n; ++k) {
        for(int j=0; j <= 2500; ++j) {
            if(j % k == 0 && j / k == a) ans += dp[n][j][k];
        }
    }

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

Measured memory_bytes: 56576
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<numeric>
#include<algorithm>
#include<complex>
#include<queue>
#include<stdlib.h>
#include<map>
#include<cmath>
#include<stdio.h>
#include<stdlib.h>
#include<set>

#define ll long long

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<pair<string,int>> vec;
    vector<pair<string,int>> vec_cp;
    string Si;
    int a;
    for(int i=0;i<N;i++){
        cin >> Si >> a;
        vec.push_back(make_pair(Si,100-a));
        vec_cp.push_back(make_pair(Si,100-a));
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(vec[i]==vec_cp[j]){
                cout << j+1 << endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip> 
#include <complex> 
#include <string>
#include <vector> 
#include <list>
#include <deque> 
#include <stack> 
#include <queue> 
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm> 
#include <numeric> 
#include <typeinfo> 
#include <cstdio>
#include <cstdlib> 
#include <cstring>
#include <cmath>
#include <climits> 
#include <ctime>

using namespace std;

int ss[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int day[13][32];

void cday(int m,int d,int dd){
	if(m==13)return;
	if(dd==8)dd=1;
	if(ss[m]==d-1)m++,d=1;
	day[m][d]=dd;
	cday(m,d+1,dd+1);
}

int main(void){
	cday(1,1,4);
	int a,b;
	while(1){
		cin >> a >> b;
		if(a==0)break;
		if(day[a][b]==1)cout << "Monday" << endl;
		if(day[a][b]==2)cout << "Tuesday" << endl;
		if(day[a][b]==3)cout << "Wednesday" << endl;
		if(day[a][b]==4)cout << "Thursday" << endl;
		if(day[a][b]==5)cout << "Friday" << endl;
		if(day[a][b]==6)cout << "Saturday" << endl;
		if(day[a][b]==7)cout << "Sunday" << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

vector<int> init(int size){
  vector<int> par(size,-1);
  return par;
}

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

bool same(int x, int y, vector<int>& par){
  return root(x, par) == root(y, par);
}

void unite(int x, int y, vector<int>& par){
  x = root(x, par), y = root(y, par);
  if(same(x,y, par))return;
  par[x] += par[y];
  par[y] = x;
}

int size(int x, vector<int>& par){
  return -par[root(x, par)];
}

signed main(){
  int n,h=0,ans=0;cin>>n;
  rep(i,n){
    int a;cin>>a;
  if(h<=a){
   ans++;
    h=a;
  }
  }
  cout<<ans;
}


Measured memory_bytes: 256
S = input()
ans=0
if S=="SUN":
    ans=7
elif S=="MON":
    ans=6
elif S=="TUE":
    ans=5
elif S=="WED":
    ans=4
elif S=="THU":
    ans=3
elif S=="FRI":
    ans=2
elif S=="SAT":
    ans=1

print (ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int palin(int x){
  int d = x / 1000;
  int dl = d / 10, dr = d % 10;
  int b = dr * 10 + dl;
  int c = (x / 100) % 10;
  if (x > 9999){
    if (x >= d * 1000 + c * 100 + b){
      return 10 * (d - 10) + c + 1;
    }
    else{
      return 10 * (d - 10) + c;
    }
  }
  else{
    return 0;
  }
}
int main(){
  int A, B;
  cin >> A >> B;
  cout << palin(B) - palin(A-1) << endl;
}

Measured memory_bytes: 256
import heapq

n = int(input())
a = list(map(int, input().split()))

# 数字から要素の場所を求められるようにdictで管理しておく
d = {}
for i, ai in enumerate(a):
    d[ai] = i

h = []

# right[i]: i<jで、a[i]>a[j]となる最も小さいjを格納する。
right = [n-1] * n

# heapqはmin-heapなので、大きい順に取り出したい時はマイナスをつけて追加して、取り出すときに要素にマイナスをつけ直す。
for i in range(n):
    while h and -h[0] > a[i]:
        v = -heapq.heappop(h)
        right[d[v]] = i - 1
    heapq.heappush(h, -a[i])

h = []
left = [0] * n

for i in reversed(range(n)):
    while h and -h[0] > a[i]:
        v = -heapq.heappop(h)
        left[d[v]] = i + 1
    heapq.heappush(h, -a[i])

ans = 0
for i in range(n):
    ans += a[i] * (i - left[i] + 1) * (right[i] - i + 1)

print(ans)

Measured memory_bytes: 47028
#include <stdio.h>
#include<math.h>
using namespace std;

int main(){
	double v,N;

	while(scanf("%lf",&v)!=EOF){
		for(int N=0;;N+=1){
			if(N >= (v*v+98)/98){
				printf("%d\n",(int)N);
				break;
			}
		}
	}

    return 0;
}

Measured memory_bytes: 2600
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define pll pair<ll,ll>
#define ld long int
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1000000000
#define N 105
#define LOG 17
#define M 2000000
#define EPS 0.0000000000001
using namespace std;

int n;
lf t[N],v[N],ans;

bool check(int now,lf sum,lf spe) {

	for(int i=now+1;i<=n+1;i++) {
		if(spe-sum>v[i]) {
			return false;
		}
		sum+=t[i];
	}
	return true;

}

int main() {

	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%lf",&t[i]);
	}
	for(int i=1;i<=n;i++) {
		scanf("%lf",&v[i]);
	}
	lf spe=0;
	for(int i=1;i<=n;i++) {
		lf bas=0,son=t[i];
		while(bas<=son) {
			if(v[i]<spe+orta) {
				son=orta-EPS;
				continue ;
			}
			lf speed=spe+orta;
			if(!check(i,t[i]-orta,speed)) son=orta-EPS;
			else bas=orta+EPS; 
		}
		ans+=son*son/2;
		ans+=spe*son;
		spe+=son;
		lf rem=t[i]-son;
		//dbg(rem);
		bas=0,son=rem;
		while(bas<=son) {
			if(!check(i,rem-orta,spe)) son=orta-EPS;
			else bas=orta+EPS;
		}
		ans+=spe*son;
		ans+=(rem-son)*(rem-son)/2;
		ans+=(rem-son)*(spe-rem+son);
		spe-=(rem-son);
		spe=min(spe,v[i+1]);
		//dbg(ans);
	}
	printf("%.12lf",ans);

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN], B[MAXN], AA[MAXN], BB[MAXN];
int par[MAXN], mark[MAXN];

int get(int x){
	return (par[x]==x?x:par[x]=get(par[x]));
}
int join(int x, int y){
	x=get(x);
	y=get(y);
	par[x]=y;
	return x!=y;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<=n; i++) cin>>A[i], A[0]^=A[i];
	for (int i=1; i<=n; i++) cin>>B[i], B[0]^=B[i];
	for (int i=0; i<=n; i++) AA[i]=A[i], BB[i]=B[i];
	sort(AA, AA+n+1);
	sort(BB, BB+n+1);
	for (int i=0; i<=n; i++) if (AA[i]!=BB[i]) kill(-1)
	m=unique(AA, AA+n+1)-AA;
	//debug(m)
	for (int i=0; i<=n; i++){
		A[i]=lower_bound(AA, AA+m, A[i])-AA;
		B[i]=lower_bound(AA, AA+m, B[i])-AA;
		if (A[i]==B[i] && i) continue ;
		mark[A[i]]=mark[B[i]]=1;
	}
	for (int i=0; i<m; i++) if (mark[i]) ans++, par[i]=i;
	for (int i=1; i<=n; i++) if (A[i]!=B[i]){
		ans++;
		ans-=join(A[i], B[i]);
	}
	ans--;
	cout<<ans<<'\n';
	
	
	return 0;
}


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

ll gcd(ll a, ll b){ 
  if(b == 0) return a;
  return gcd(b, a % b);
}

ll lcm(ll a, ll b){ 
  return a * b / gcd(a, b);
}

int main(){
  int A,B;
  cin >> A >> B;
  cout << lcm(max(A,B), min(A,B)) << endl;
}


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

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

string arrange(string s) {
    int m = s.size();
    string t = "";
    rep(i,m) {
        int j, cnt = 0;
        for(j=i; j<m and s[j]==s[i]; j++) cnt++;
        t += to_string(cnt) + s[i];
        i = j-1;
    }
    return t;
}

int main() {
    int n;
    while(cin>>n && n) {
        string s;
        cin >> s;
        rep(i,n) s = arrange(s);
        cout << s << endl;
    }

    return 0;
}

Measured memory_bytes: 3388
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdint>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

// input
uint64_t getZ() {
  uint64_t v = 0; int c;
  while((c = getchar_unlocked()) >= '0') v=v*10+c-'0';
  return v;
}

int const MAXN = 2e5;

std::vector<int> G[MAXN];

int64_t ans[MAXN];

void dfs(int v, int p) {
  for(auto c: G[v]) if(c!=p) {
    ans[c] += ans[v];
    dfs(c, v);
  }
}

int main() {
  int N = getZ(), Q = getZ();
  for(int i = 0; i < N-1; ++i) {
    int a = getZ()-1, b = getZ()-1;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  std::fill_n(ans, N, 0);
  for(int i = 0; i < Q; ++i) {
    int p = getZ()-1;
    ans[p] += getZ();
  }
  dfs(0, -1);
  for(int i = 0; i < N-1; ++i) std::cout << ans[i] << " ";
  fin(ans[N-1]);
  return 0;
}


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

using namespace std;

const int MAXN = 1000000;
int A[MAXN + 1];

int f(int n) {
	if (n % 2 == 0) {
		return n / 2;
	} else {
		return 3 * n + 1;
	}
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int s, count = 1;
  cin >> s;

  for (int i = 0; i < MAXN + 1; i++) {
  	A[i] = 0;
  }

  A[s] += 1;
  while (true) {
  	s = f(s);
  	count++;
  	if (A[s] != 0) {
  		cout << count << '\n';
  		break;
  	}
  	A[s]++;
  }
  return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional>
#define ll long long int
#define ld long double
#define pb push_back
#define pll pair<ll,ll>
#define pint pair<int,int>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define mod 1000000007
#define MAX 100000000
#define endl '\n'
#define mp make_pair
#define INF INT_MAX
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ff first
#define ss second
#define ps(x,y) fixed<<setprecision(y)<<x
#define setbits(x) __builtin_popcountll(x)            //counts no of ones in binary representation
#define w(t)     int t; cin>>t; while(t--)
#define pi 3.141592653589793238
#define sortt(v)  sort(v.begin(),v.end())
#define lb(v,x) std::lower_bound(v.begin(),v.end(),x)
#define ub(v,x) std::upper_bound(v.begin(),v.end(),x)

using namespace std;

int main(){
    fast;
    ll n;
    cin>>n;
    ll a[n];
    forn(i,n)	cin>>a[i];
    sort(a,a+n);
    ll ans=0;
    if(n%2){
    	int x=n/2;
    	for(int i=n-1;i>=n-x;i--)	ans+=a[i];
    	for(int i=n-2;i>=n-1-x;i--)		ans+=a[i];
    	cout<<ans;
	}
	else{
		int x=n/2;
		x--;
    	for(int i=n-1;i>=n-x;i--)	ans+=a[i];
    	for(int i=n-2;i>=n-1-x;i--)		ans+=a[i];
    	ans+=a[n-1-x];
    	cout<<ans;
	}
}

Measured memory_bytes: 5192
///
// File:  alds1_12_b.cpp
// Author: ymiyamoto
//
// Created on Wed Oct 18 21:59:56 2017
//

#include <cstdint>
#include <iostream>

using namespace std;
#define SIZE 100
static int64_t graph[SIZE][SIZE];
static int64_t costs[SIZE];
static bool visited[SIZE];

static void dikstra(uint32_t n)
{
  costs[0] = 0;

  while (true) {
    int32_t min_index = -1;
    int64_t min_cost = INT32_MAX;

    for (uint32_t i = 0; i < n; i++) {
      if (!visited[i] && costs[i] < min_cost) {
        min_cost = costs[i];
        min_index = i;
      }
    }

    if (min_index == -1) break;

    visited[min_index] = true;

    for (uint32_t i = 0; i < n; i++) {
      if (graph[min_index][i] != -1) {
        if (costs[min_index] + graph[min_index][i] < costs[i]) {
          costs[i] = costs[min_index] + graph[min_index][i];
        }
      }
    }
  }
}

int32_t main()
{
  uint32_t n;
  cin >> n;

  for (uint32_t i = 0; i < n; i++) {
    for (uint32_t j = 0; j < n; j++) {
      graph[i][j] = -1;
    }
    costs[i] = INT32_MAX;
  }

  for (uint32_t i = 0; i < n; i++) {
    uint32_t id, k;
    cin >> id >> k;
    for (uint32_t j = 0; j < k; j++) {
      int64_t v, c;
      cin >> v >> c;
      graph[id][v] = c;
    }
  }

  dikstra(n);

  for (uint32_t i = 0; i < n; i++) {
    cout << i << " " << costs[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)

#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;


const int INF = 1<<29;        // 十分大きい値にする, INT_MAX にしないのはオーバーフロー対策
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 a,b,c;
    cin >> a >> b >> c;
    cout << c << " " << a  << " " << b << endl;
}   

Measured memory_bytes: 256
from collections import deque
import sys
sys.setrecursionlimit(10**7)
 
N,M=map(int,input().split())
Graph=[[] for i in range(N)]
for i in range(M):
  L,R,D=map(int,input().split())
  Graph[L-1].append((R-1,D))
  Graph[R-1].append((L-1,-D))
visit=[False]*N
dist=[0]*N
 

for i in range(N):
  if not visit[i]:
    visit[i]=True
    A=deque()
    A.append(i)
    while A:
      x=A.pop()
      for y,d in Graph[x]:
        if visit[y] and (dist[y]!=d+dist[x]):
          print('No')
          exit()
        elif not visit[y]:
          visit[y]=True
          A.append(y)
          dist[y]=d+dist[x]
print('Yes')

Measured memory_bytes: 67100
#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>;
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(x) x.begin(),x.end()
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

int n,m;
ll solve(){
   ll ans=0;
   ans=(1900*m+100*(n-m))*pow(2,m);

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

    cin>>n>>m;
    cout<<solve()<<endl;
    return 0;
}

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

int main(){
	int N, i;
	scanf("%d", &N);
	vector<int> a(N);
	for(i = 0; i < N; i++){
		scanf("%d", &a[i]);
		a[i]--;
	}
	int now = 0, ans = 0;
	for(i = 0; i <= N; i++){
		now = a[now];
		ans++;
		if(now == 1){
			printf("%d\n", ans);
			return 0;
		}
	}
	printf("-1\n");
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, a[25], b[25], c[25], ans;
int main() {
   cin >> n;
   for (int i=0; i<n; i++) {cin >> a[i]; a[i]--;}
   for (int i=0; i<n; i++) cin >> b[i];
   for (int i=0; i<n-1; i++) cin >> c[i];
   
   for (int i=0; i<n; i++) {
       ans+=b[a[i]];
       if (i>0) {
           if (a[i]==a[i-1]+1) ans+=c[a[i-1]];
       }
   }
   cout << ans;
}

Measured memory_bytes: 3608
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring> 
#include<cassert>
#include<cmath>
#include<sstream>
#include<fstream>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
string s;
vector<string> ss;
int main(){
	cin>>s;
	string tmp1,tmp2;
	tmp1+=s[0];
	ss.push_back(tmp1);
	int cnt1=1,cnt2=1;
	for(int i=1;i<s.size();i++){
		tmp2+=s[i];
		if(tmp2!=tmp1){
			cnt1++;
//			cout<<tmp1<<" "<<tmp2<<endl;
			tmp1=tmp2;
			ss.push_back(tmp1);
			tmp2.clear();
		}
	}
	if(tmp1==tmp2){
		if((ss.size()>=2&&ss[ss.size()-2]==tmp1+tmp2)||ss.size()<2) cnt1--;
	}
	tmp1.clear();tmp2.clear();
	ss.clear();
	tmp1+=s[s.size()-1];tmp1+=s[s.size()-2];
	ss.push_back(tmp1);
	for(int i=s.size()-3;i>=0;i--){
		tmp2+=s[i];
		if(tmp2!=tmp1){
			cnt2++;
			tmp1=tmp2;
			tmp2.clear();
		}
	}
	if(tmp1==tmp2){
		if((ss.size()>=2&&ss[ss.size()-2]==tmp1+tmp2)||ss.size()<2) cnt2--;
	}
	cout<<max(cnt1,cnt2);
}

Measured memory_bytes: 10996
#![allow(unused_imports)]
use itertools::Itertools;
use num::integer::lcm;
use proconio::{input, marker::*};
use std::cmp::*;
use std::collections::*;
use superslice::*;

fn main() {
    input! {
        a: u64,
        b: u64
    }

    println!("{}", lcm(a, b));
}


Measured memory_bytes: 2124
#include <cstdio>
int n, cnt, a[100005];
int main() {
	int i;
	scanf("%d", &n);
	for(i=1; i<=n; i++) scanf("%d", a+i);
	for(i=1; i<=n; i++) cnt += a[a[i]] == i;
	printf("%d", cnt/2);
	return 0;
}

Measured memory_bytes: 512