akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <tuple>
#include <algorithm>
#include <functional>

template <class T>
T abs(T a) { return (a > 0 ? a : -a); }

template <class T>
T root(std::vector<T>& v, T x) {
    if (v[x] == x) return x;
    else return v[x] = root(v, v[x]);
}

template <class T>
bool same (std::vector<T>& v, T x, T y) {
    return root(v, x) == root(v, y);
}

template <class T>
void unite(std::vector<T>& v, T x, T y) {
    x = root(v, x);
    y = root(v, y);
    if (x == y) return;
    v[x] = y;
}

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

    /* cost, i, j */
    using T = std::tuple<long long, long long, long long>;
    std::priority_queue<T, std::vector<T>, std::greater<T>> pq;

    {
        std::priority_queue<std::pair<long long, long long>> cx, cy;
        for (auto i = 0ll; i < n; i++) {
            long long x, y;
            std::cin >> x >> y;
            cx.push(std::make_pair(x, i));
            cy.push(std::make_pair(y, i));
        }

        auto px = cx.top(), py = cy.top();
        cx.pop();
        cy.pop();
        for (auto i = 1ll; i < n; i++) {
            auto &currx = cx.top(), &curry = cy.top();
            pq.push(std::make_tuple(px.first - currx.first, px.second, currx.second));
            pq.push(std::make_tuple(py.first - curry.first, py.second, curry.second));
            px = currx;
            py = curry;
            cx.pop();
            cy.pop();
        }
    }

    std::vector<long long> par(n);
    for (auto i = 0ll; i < n; i++) par[i] = i;

    long long ret = 0, count = 0;
    std::vector<bool> done(n, false);
    while (count < n - 1) {
        auto& curr = pq.top();
        //std::cout << std::get<0>(curr) << " " << std::get<1>(curr) << " " << std::get<2>(curr);
        auto fst = std::get<1>(curr), snd = std::get<2>(curr);
        if (!same(par, fst, snd)) {
            //std::cout << " Add";
            ret += std::get<0>(curr);
            count++;
            unite(par, fst, snd);
        }
        pq.pop();
        //std::cout << std::endl;
    }

    std::cout << ret << std::endl;

    return 0;
}

Measured memory_bytes: 13024
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let _c: usize = read();
    let mut tvs = vec![(0, 0, 0); n];
    for i in 0..n {
        tvs[i].0 = read();
        tvs[i].1 = read();
        tvs[i].2 = read();
    }
    tvs.sort_by(|a, b| (a.2, a.0).cmp(&(b.2, b.0)));
    let mut merged_tvs = vec![];
    for i in 0..tvs.len() {
        if i != 0 && tvs[i - 1].2 == tvs[i].2 && tvs[i - 1].1 == tvs[i].0 {
            continue;
        }
        let mut offset = 1;
        let mut tv = tvs[i].clone();
        while i + offset < n {
            let ntv = tvs[i + offset];
            if tv.2 != ntv.2 || tv.1 != ntv.0 {
                break;
            }
            tv.1 = ntv.1;
            offset += 1;
        }
        merged_tvs.push(tv);
    }
    merged_tvs.sort();
    // println!("{:?}", merged_tvs);
    let mut recs: Vec<(usize, usize, usize)> = vec![];
    'tv_loop: for tv in merged_tvs {
        for i in 0..recs.len() {
            if recs[i].1 < tv.0 {
                // println!("{} {:?} {:?}", i, recs[i], tv);
                recs[i] = tv;
                continue 'tv_loop;
            }
        }
        recs.push(tv);
    }
    println!("{}", recs.len());
}


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

int main() {
        int H[10000], W[10000], i, a, k;
        i = 100000;
        a = 0;
        k = 0;
        for (k; k < i; k++) {
                cin >> H[k] >> W[k];
                if (H[k] == 0 && W[k] == 0) break;
        }
        for (int j = 0; j < k; j++) {
                for (int l = 1; l < H[j] + 1; l++) {
                        for (int m = 1; m < W[j] + 1; m++) {
                                cout << "#";
                        }
                        cout << endl;
                }
                cout << endl;
        }

}

Measured memory_bytes: 3048
fun main(args : Array<String>){
    var (n,k)=readLine()!!.split(" ").map(String::toInt)
    var sunuke = Array<Boolean>(n,{false})
    for (i in 1..k){
        var okashi=readLine()!!.toInt()
        var array = readLine()!!.split(" ").map(String::toInt)
        for (a in array){
            sunuke[a-1] = true
        }
    }
    
    var ans = 0
  	sunuke.filter { it == false }.forEach { ans++ }
    print(ans.toString())
}

Measured memory_bytes: 38876
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin>>N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  int ans=N;
  sort(A.begin(), A.end());
    int s=0;
    int t=N-1;
  while(true){
    int flag=0;
    while(s<t){
      if(A[s]==A[s+1]){
        flag=1;
        s++;
        break;
      }
      s++;
    }
    while(s<t){
      if(A[t]==A[t-1]){
        t--;
        break;
      }
      t--;
    }
    
    if(flag==1){
      ans-=2;
      continue;
    }
    else if(flag==0){
      break;
    }
  }
  cout<<ans;
}

Measured memory_bytes: 640
import sys
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    a_max = max(A)
    max_count = A.count(a_max)
    for a in A:
        if a != a_max:
            print(a_max)
        elif max_count > 1:
            print(a_max)
        else:
            B = A[:]
            B.remove(a_max)
            print(max(B))

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 33440
/*

*/
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((ll)(x).size())
#define cin1(x) cin >> x
#define cin2(x, y) cin >> x >> y
#define cin3(x, y, z) cin >> x >> y >> z
#define cou(x) cout << x
#define cous(x) cout << x << " "
#define coul(x) cout << x << "\n"
#define ret(x) return x
#define MAX 5000001
#define start int main() {   fastio
#define finish ret(0); }
#define Test ll _t; cin1(_t); while( _t-- )
typedef long long ll;
typedef vector<ll> VI;
typedef pair<ll,ll> PII;
typedef double db;
//mt19937 mrand(random_device{}());
const ll mod=1000000007;
//ll rnd(ll x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}ret(res);}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll fact[13];
void factorial() {   fact[0]=1;  rep(i, 1, 12) fact[i]=(fact[i-1]*i);  }
vector <ll> sie; //for sieve function
ll spf[MAX+7];  //for sieve function
void sieve() {    rep(i, 2, MAX)  {  if (spf[i] == 0) {  spf[i] = i;   sie.pb(i);  }    for (ll j=0; j<SZ(sie) && i*sie[j] <= MAX && sie[j] <= spf[i]; j++)   spf[i * sie[j]] = sie[j]; }   }
// head collected

start;
    ll n, m, ans, an;
    cin2(n, m);

    ans = (n*(n-1))/2;
    an = (m*(m-1))/2;

    coul(ans+an);
finish





Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main(int argc, char const *argv[]) {
string A,B;
cin>>A>>B;
if(A.size()>B.size()){
  cout<<"GREATER"<<endl;
}else if(A.size()<B.size()){
  cout<<"LESS"<<endl;
}else{
  for(size_t i=0;i<A.size();i++){
    if(A[i]>B[i]){
        cout<<"GREATER"<<endl;
        return 0;
    }else if(A[i]<B[i]){
      cout<<"LESS"<<endl;
      return 0;
    }
  }
  cout<<"EQUAL"<<endl;
}

  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i=0; i<N; i++) {
			int a = sc.nextInt();
			Integer count = map.get(a);
			if(count==null)
				count = 0;
			map.put(a, count+1);
		}
		
		int ans = 0;
		for(Integer key : map.keySet()) {
			if(map.get(key)<key)
				ans += map.get(key);
			else
				ans += (map.get(key) - key);
		}
		
		System.out.println(ans);
				
		sc.close();
	}
}


Measured memory_bytes: 60304
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

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

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
#define REP(i,n) for(ll i=0; i<(n); i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define ALL(n) begin(n),end(n)
#define IN(a, x, b) (a<=x && x<b)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T & a, const T b) { return a = (a > b) ? b : a; }

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
const long long MOD = 1000000007;

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

Measured memory_bytes: 3548
#include <stdio.h>		// standard input output
#include <iostream>		// input output stream, cin cout( console in console out)
#include <cmath>		// circle math ( sin, con, sinh
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>		// input output manipulation

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rep3(i, a, n) for(int i = (int)(a); i < (int)(n); i++)
#define ll long long

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }






int main() {
  ll N,M,K; // 変数の宣言
  cin >> N >> M >> K; // 標準入力
  ll a[N+1],b[M+1];
  a[0]=0;b[0]=0;
  int t;
  rep(i,N) {
    cin >> t;
    a[i+1]=a[i]+t;
  }
  rep(i,M) {
    cin >> t;
    b[i+1]=b[i]+t;
  }
  
  ll ans =0;
  ll j=M;
  rep(i,N+1){
    if(a[i]>K) break;
    while(a[i] + b[j]>K){
      
        j--;
    }
    ans = max(ans,i+j);
  }
  cout << ans << endl; // 標準出力
	
}


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

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

using ll=long long;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const ll MOD=1e9+7;

int main(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    multiset<int> ms;
    for(int i=0; i<N; i++){
        cin >> A[i];
        ms.insert(A[i]);
    }
    ll res=0;
    for(int i=0; i<M; i++){
        int num=*(ms.rbegin());
        ms.erase(ms.find(num));
        ms.insert(num/2);
    }
    for(auto x : ms){
        res+=x;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 8748
#include<bits/stdc++.h>
using namespace std;
typedef		long long       ll;
typedef         long double      dl;
#define		pb              push_back
#define		PB              pop_back
#define		nn              "\n"
#define     O_O             ios_base::sync_with_stdio(false); cin.tie(NULL)
#define		all(p)          p.begin(),p.end()
#define		zz(v)           (ll)v.size()
#define		ss              ' '
#define         arrsize(a)      (sizeof(a)/sizeof(a[0]))
//#define       arrsize(a)      (sizeof(a)/sizeof(*a))
#define 	S(a)            scanf("%lld",&a)
#define 	SS(a,b)         scanf("%lld %lld",&a,&b)
#define 	SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define		gcd(a,b)        __gcd(a,b)
#define		lcm(a,b)        (a*b)/gcd(a,b)
#define		pi              acos(-1.0)
typedef        pair <int, int>   pii;
typedef       pair <ll, ll>      pll;
typedef      vector< pair <ll, ll>>      vpll;
typedef		vector<ll>      vll;


int main()
{
 //O_O ;
   ll t,n;
   cin>>t>>n;
   if(t%n==0)
    cout<<t/n<<nn;
   else
    cout<<(t/n)+1<<nn;

    return 0;
}


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

int main(){
  string s;
  cin >> s;
  string t="CODEFESTIVAL2016";
  int res=0;
  for(int i=0;i<t.size();++i){
    if(s[i]!=t[i])res++;
  }
  cout<<res<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> //__gnu_pbds::gp_hash_table<int, int> table;
//priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  //min heap

typedef int OwO;
typedef double UwU;

#define int long long
#define double long double
#define INF 1000000000
#define PI 3.14159265358979323846
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vvi vector<vector<int>>
#define vi vector<int>

using namespace std;

OwO main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  double N;
  vector<double> c(6);
  vector<double> t(5);
  cin >> N >> t[0] >> t[1] >> t[2] >> t[3] >> t[4];
  sort(t.begin(), t.end());
  double p1 = min(t[0], N);
  cout << fixed << (int)ceil(N/p1+4.0) << endl;
  return 0;
}

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

int main() {
  int A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;

  long double conc = -1;
  int water = 0, sugar = 0;

  for (int i = 0; i <= F; i += 100 * A) {
    for (int j = 0; i + j <= F; j += 100 * B) {
      int a = i + j;
      int div_a = (i + j) / 100;
      for (int k = 0; k <= div_a * E; k += C) {
        for (int l = 0; k + l <= div_a * E; l += D) {
          int b = k + l;
          if (a + b == 0 || a + b > F) continue;
          if (conc < double(100 * b) / double(a + b)) {
            conc = double(100 * b) / double(a + b);
            water = a;
            sugar = b;
          }
        }
      }
    }
  }

  cout << water + sugar << ' ' << sugar << endl;
}

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

const int MAX_N = 3000;
const int MOD = 1e9 + 7;
struct I {
  int v;
  operator int() { return v; }

  I operator+(const I &rhs) const {
    return {v + rhs.v >= MOD ? v + rhs.v - MOD : v + rhs.v};
  }
} f[MAX_N + 1], pre[MAX_N + 1], suf[MAX_N + 2];

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int n;
  std::cin >> n;
  f[1] = pre[1] = suf[1] = {1};
  while (isspace(std::cin.rdbuf()->sgetc())) std::cin.rdbuf()->sbumpc();
  for (int i = 2; i <= n; ++i) {
    memcpy(f + 1, std::cin.rdbuf()->sbumpc() == '<' ? pre : suf + 1,
           sizeof(I) * (i));
    for (int j = 1; j <= i; ++j) pre[j] = pre[j - 1] + f[j];
    for (int j = i; j; --j) suf[j] = suf[j + 1] + f[j];
  }
  std::cout << pre[n];
}

Measured memory_bytes: 256
//
//  main.cpp
//  ITP1_10-C
//
//  Created by Saicj on 2015/08/05.
//  Copyright (c) 2015??´ saicj. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>

using namespace std;


int main(int argc, const char * argv[]) {
    
    double n;
    
    double num;
    
    
    while (true) {
        
        cin >> n;
        
        std::vector<double> nums(n);
        
        if (n == 0){
            break;
        }
        
        for (int i = 0; i < n; i++) {
            
            cin >> num;
            nums[i] = num;
        }
        
//        cout << "nums[0]" << nums[0] << endl;
        
        double sum = 0;
        
        for (int i = 0; i < n; i++){
            sum +=nums[i];
        }

//        cout << sum << endl;
        
        double m = sum/n;
        
//        cout << "m:" << m << endl;
        
        double mSum = 0;
        for (int i = 0; i < n; i++) {
            mSum += pow(nums[i]-m, 2);
            
//            cout << i << ":" << mSum << endl;
        }
        
//        cout << "mSum:" << mSum << endl;
        
        double result = sqrt(mSum/n);
        
        printf("%.8lf \n", result);
        
    }
    
    return 0;
}

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

/* メモリ食い過ぎ注意 */
#define int long long

typedef long long ll;

ll gcd(ll a, int b)
{
    if (a < b)
        gcd(b, a);
    if (b == 0)
        return a;
    int r;
    while ((r = a % b))
    {
        a = b;
        b = r;
    }
    return b;
}

/* define const */
const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;
/* end defineing */

signed main()
{
    int n, k;
    cin >> n >> k;

    ll ret = 1;
    for (int i = 0; i < n; i++)
    {
        ret = min(ret * 2, ret + k);
    }
    cout << ret << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define REP(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

#define ALL(x) (x).begin(),(x).end()
typedef long long ll;

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev

int main(){
  int N;
  cin >> N;
  int A[N-1];
  REP(i,N-1) cin >> A[i];
  
  int ans[N] = {0};
  REP(i,N-1) ans[A[i]-1] += 1;
  
  REP(i,N) cout << ans[i] << endl;

  return 0;
}

Measured memory_bytes: 5160
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
int board[25] [25], n;
long long dp[21] [1 << 21];
long long DP(int at, int mask){
    if(at == n)
        return 1;
    long long& k = dp[at] [mask];
    if(k != -1)
        return k;
    k = 0;
    for(int i = 0; i < n; i++)
        if(board[at] [i] == 1 && !(mask & (1 << i)))
            k =(k % mod + DP(at + 1, mask | (1 << i)) % mod) % mod;
    return k;
}
int main( ){
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> board[i] [j];
    memset(dp, -1, sizeof dp);
    long long ans = DP(0, 0);
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 347680
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<cmath>

#define rep(i,x) for(int i=0;i<(int)(x);i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)

#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 2e12

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; }
typedef long long ll;
typedef std::pair<ll, ll> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

using namespace std;

int main()
{
    ll a, b;
     cin >> a >> b;

     ll p0 = (a * 100 + 7) / 8;
     ll p1 = (a * 100 + 99) / 8;
     ll q0 = (b * 100 + 9) / 10;
     ll q1 = (b * 100 + 99) / 10;

     ll flag = -1;

     for(ll i = p0; i<= p1; i++){
         for(ll j = q0; j <= q1; j++){
             if(i == j){
                 flag = i;
                 cout << flag << endl;
                 return 0;
             } 
         }
     }
     cout << "-1" << endl;
     return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include <time.h>
typedef long long ll;
typedef long double ld;
#define INF (1LL<<60)
#define MOD1 1000000007
/*swap 交換*/
void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
/*2つのうち大きい数を返す*/
ll max2(ll a,ll b){return a>=b?a:b;}
/*2つのうち小さい数を返す*/
ll min2(ll a,ll b){return a>=b?b:a;}
/*絶対値*/
ll ABS(ll a){return a>=0?a:(-a);}
typedef struct{
	ll aa;
	ll bb;
}frequent;
// 小大
int compare(const void *a, const void *b){
	return *(ll *)a>*(ll *)b?1:*(ll *)a<*(ll *)b?-1:0;}
ll arrived[8][8];
ll ok(ll h,ll w,ll x,ll y){
	if(x<0||x>w-1) return 0;
	if(y<0||y>h-1) return 0;
	return 1;
}
ll dfs(ll h, ll w, ll x, ll y, char s[h][w]){
	printf("%lld %lld\n",x,y);
	arrived[x][y]=1;
	if(x==w-1&&y==h-1) return 0;
	if(ok(h,w,x-1,y)){
		if( arrived[x-1][y]!=1 && s[x-1][y]=='#'){
			return 1;
		}
	}
	if(ok(h,w,x,y-1)){
		if( arrived[x][y-1]!=1 && s[x][y-1]=='#'){
			return 1;
		}
	}
	if(ok(h,w,x+1,y+1)){
		if( s[x+1][y]=='#' && s[x][y+1]=='#'){
			return 1;
		}
	}
	return ok(h,w,x+1,y)?dfs(h,w,x+1,y,s):dfs(h,w,x,y+1,s);
}

int main(void){
	ll h,w,i,j,count=0;
	scanf("%lld%lld",&h,&w);
	char s[h][w];
	for(i=0;i<h;i++){
		scanf("%s",s[i]);
		for(j=0;j<w;j++){
			if(s[i][j]=='#') count++;
		}
	}
	if( count==h+w-1){
		printf("Possible\n");
	}else{
		printf("Impossible\n");
	}
	return 0;
}


Measured memory_bytes: 128
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for(int i = 0; i < n; i++) {
			Vector2D A = new Vector2D(sc.nextInt(),sc.nextInt());
			Vector2D B = new Vector2D(sc.nextInt(),sc.nextInt());
			Vector2D C = new Vector2D(sc.nextInt(),sc.nextInt());
			Vector2D K = new Vector2D(sc.nextInt(),sc.nextInt());
			Vector2D S = new Vector2D(sc.nextInt(),sc.nextInt());
			boolean KB = hittestPointPolygon2D(A, B, C, K);
			boolean SB = hittestPointPolygon2D(A, B, C, S);
			boolean ans = false;
			if(KB && SB) {
				ans = false;
			}
			else if(KB || SB) {
				ans = true;
			}
			
			System.out.println((ans)?"OK":"NG");
		}
	}
	
	static class Vector2D {
		int x;
		int y;
		Vector2D(int a, int b) {
			x = a;
			y = b;
		}
		Vector2D() {
			x = 0;
			y = 0;
		}
	}
	
	static Vector2D sub_vector(Vector2D a, Vector2D b) {
		Vector2D ret = new Vector2D();
		ret.x = a.x - b.x;
		ret.y = a.y - b.y;
		return ret;
	}
	
	static boolean hittestPointPolygon2D(Vector2D A, Vector2D B, Vector2D C, Vector2D P) {
		Vector2D AB = sub_vector(B, A);
	    Vector2D BP = sub_vector(P, B);

	    Vector2D BC = sub_vector(C, B);
	    Vector2D CP = sub_vector(P, C);

	    Vector2D CA = sub_vector(A, C);
	    Vector2D AP = sub_vector(P, A);

	    int c1 = AB.x * BP.y - AB.y * BP.x;
	    int c2 = BC.x * CP.y - BC.y * CP.x;
	    int c3 = CA.x * AP.y - CA.y * AP.x;

	    if( ( c1 > 0 && c2 > 0 && c3 > 0 ) || ( c1 < 0 && c2 < 0 && c3 < 0 ) ) {
	        return true;
	    }

	    return false;
	}
	
	
	

}

Measured memory_bytes: 63024
#include<stdio.h>

int main(){
	int n;
	scanf("%d", &n);
	
	long long int sum = 0;
	
	for(int i = 1 ; i <= n; i++){
		if(i % 3 == 0 || i % 5 == 0){
			continue;
		}
		else{
			sum += i;
		}
	}
	printf("%lld", sum);
	return 0;
}


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

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int N; string s,t;
	cin>>N>>s>>t;
	int c = min(s.size(),t.size());
	int e_ans = 0;
	rep(i,c+1){
		string tt = s.substr(s.size()-i,i);
		if(tt == t.substr(0,i))e_ans = i;
	}
	cout<<max(N, (int)(s.size()+t.size())-e_ans)<<endl;
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  int G[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      G[i][j] = 0;
    }
  }
  for (int i = 0; i < n; i++) {
    int vi, out_v_num;
    cin >> vi;
    cin >> out_v_num;
    for (int j = 0; j < out_v_num; j++) {
      int out_vi;
      cin >> out_vi;
      G[vi-1][out_vi-1] = 1;
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (j) cout << " ";
      cout << G[i][j];
    }
    cout << endl;
  }
}



Measured memory_bytes: 3096
N = int(input())
lr = [[0,0]]*N

for i in range(N):
    X,L = map(int,input().split())
    lr[i] = [X-L,X+L]
lr_s = sorted(lr)

ans = 1
now_r = lr_s[0][1]

for i in range(1,N):
    next_l = lr_s[i][0]
    next_r = lr_s[i][1]
    if now_r > next_l: #かぶってるときは右端が小さい方を残す
        now_r = min(now_r,next_r)
        #ロボットの数の増減はプラマイゼロ
    else:
        #かぶってないときはロボットが増える
        ans += 1
        now_r = next_r
        
print(ans)

Measured memory_bytes: 56364
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  int n;
  cin >> n;
  int v[n];
  for (int i = 0; i < n; i++)
    cin >> v[i];
  int e[100001] = {};
  int o[100001] = {};
  for (int i = 0; i < n; i++)
  {
    if (i % 2 == 0)
      e[v[i]]++;
    else
      o[v[i]]++;
  }
  int e_max1 = 0;
  int e_max2 = 0;
  int o_max1 = 0;
  int o_max2 = 0;
  for (int i = 1; i <= 100000; i++)
  {
    if (e[e_max1] < e[i])
      e_max1 = i;
    if (o[o_max1] < o[i])
      o_max1 = i;
  }
  for (int i = 1; i <= 100000; i++)
  {
    if (e[e_max2] <= e[i] && i != e_max1)
      e_max2 = i;
    if (o[o_max2] <= o[i] && i != o_max1)
      o_max2 = i;
  }
  int ans = 0;
  if (e_max1 == o_max1)
  {
    int ans1 = 0;
    int ans2 = 0;
    for (int i = 0; i < n; i++)
    {
      if ((i % 2 == 0 && v[i] != e_max1) || (i % 2 == 1 && v[i] != o_max2))
        ans1++;
      if ((i % 2 == 0 && v[i] != e_max2) || (i % 2 == 1 && v[i] != o_max1))
        ans2++;
    }
    ans = min(ans1, ans2);
  }
  else
  {
    for (int i = 0; i < n; i++)
    {
      if ((i % 2 == 0 && v[i] != e_max1) || (i % 2 == 1 && v[i] != o_max1))
        ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;

#define MAX_E 100000
#define MAX_V 100000

struct edge {
	int from, to, cost;
};
int d[MAX_V];
int V, E;

edge es[MAX_E];

void shortest_path(int s) {
	rep(i, 0, V) d[i] = INF;
	d[s] = 0;
	while(true) {
		bool update = false;
		rep(i, 0, E) {
			edge e = es[i];
			if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if(!update) break;
	}
}

bool find_negative_loop(int s) {
	//memset(d, 0, sizeof(d));
	fill(d, d + V, INF);
	d[s] = 0;
	rep(i, 0, V) {
		rep(j, 0, E) {
			edge e = es[j];
			if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				if(i == V - 1) return true;
			}
		}
	}
	return false;
}

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

	int r;
	cin >> V >> E >> r;
	rep(i, 0, E) {
		int s, t, d;
		cin >> s >> t >> d;
		es[i].from = s;
		es[i].to = t;
		es[i].cost = d;
	}

	if(find_negative_loop(r)) {
		cout << "NEGATIVE CYCLE" << endl;
		return 0;
	}

	rep(i, 0, V) {
		if(i == r || d[i] != INF) cout << d[i] << endl;
		else cout << "INF" << endl;
	}
}



Measured memory_bytes: 3212
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

llong POW(llong a, llong b){
	if(b == 0) return 1;
	else{
		if(b%2 == 0) return POW(a * a % MOD, b / 2) % MOD;
		else return a * POW(a * a % MOD, b / 2) % MOD;
	}
}

llong COMB(llong a, llong b){
	llong ans = 1;
	for(llong i=1; i<=b; ++i){
		ans *= a+1-i;
		ans %= MOD;
		ans *= POW(i, MOD-2);
		ans %= MOD;
	}
	return ans;
}

int main(){
	llong K;
	cin >> K;
	string S;
	cin >> S;
	llong SIZE = S.length();
	llong ans = 0;
	llong comb = COMB(K+SIZE-1, SIZE-1) % MOD;
	for(llong i=0; i<=K; ++i){
		if(i!=0){
			comb *= POW(K+SIZE-1-i+1, MOD-2);
			comb %= MOD;
			comb *= K-i+1;
			comb %= MOD;
		}
		ans += comb % MOD * POW(25, K-i) % MOD * POW(26, i) % MOD;
		ans %= MOD;
	}
	if(ans < 0) ans += MOD;
	cout << ans << endl;
}

Measured memory_bytes: 5328
/*  ex4_2
    potter0723sw  */

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main(void) {
    double lengtha,lengthb,hour,minute,radian,mid,ans;
    scanf("%lf %lf %lf %lf", &lengtha, &lengthb, &hour, &minute);
    radian = fabs(5.5 * minute - 30 * hour) * M_PI / 180;//5.5は6-0.5で長針の1分6度の動きから短針の1分0.5度の動きの差をとったもの
    mid = pow(lengtha,2)+ pow(lengthb,2) - 2*lengtha*lengthb * cos(radian);//余弦定理
    ans = sqrt(mid);//平方根をとって答え
    printf("%15.10lf\n", ans);
    return 0;
}

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

using ll = long long;
#define mod 1000000007


int main() 
{
	ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll n;
    cin>>n;
    vector<pair<ll,ll>> arr(n);
    for(ll i=0;i<n;i++)
    {
    	ll a,b;
    	cin>>a>>b;
    	arr[i]={a,b};
    }
    ll i=0;
    while(i<n)
    {
    	ll c=1;
    	if(arr[i].first==arr[i].second)
    	{
    		while(i+1<n and arr[i+1].first==arr[i+1].second)
    		{
    			i++;
    			c++;
    			if(c>=3)
    			{
    				cout<<"Yes"<<endl;
    				return 0;
    			}
    		}
    	}
    	i++;
    }
    cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<tuple>
#include<string>
typedef long long int ll;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define F first
#define S second
using namespace std;
const ll INF = 10000000000000;

int main() {
  vector<char> s(3);
  vector<char> t(3);
  rep(i,0,3)cin>>s[i];
  int ans=0;
  rep(i,0,3){
    cin>>t[i];
    if(s[i]==t[i])ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
// 6/26 解き直し
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;

int main() {
    double a, b, x;
    cin >> a >> b >> x;

    double ans;

    if (x >= a * a * b / 2.0) {
        // 台形の形からこぼれ始める。
        ans = atan(2.0*(a*a*b-x)/(a*a*a));
    } else {
        ans = (M_PI/2.0) - atan(2.0*x/(a*b*b));
    }

    cout << fixed << setprecision(15);
    cout << ans * 180.0 / M_PI << endl;
}

Measured memory_bytes: 4076
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
int prodmod(vector<int> w);
int summod(vector<int> w);
///CUIDADO COM MAXN
#define N 300050

int n, m, q, k, v[N], ans;
pii w[N];
string s;

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>v[i];
	sort(v+1,v+n+1);
	reverse(v+1,v+n+1);
	for(int i=2;i<=n;i++){
		ans += v[(i+1)/2];
	}
	cout<<ans<<"\n";
}
/*
    CUIDADO COM MAXN, MOD, OVERFLOW 
    >Colocar (>DEFINE INT LONG LONG<) no inicio do template
    >mod = (1e9 + 7), por padrao (NAO ESQUECER DE ALTERAR)
    >NAO ESQUECER DEFINE INT LONG LONG
    > N = 1 ? 
*/
int summod(vector<int> w){int curr=0;for(int i=0;i<sz(w); i++){curr = (curr+w[i])%mod;if(curr<0)curr+=mod;}return curr;}
int prodmod(vector<int> w){int curr = 1;
for(int i = 0; i < sz(w); i++){if(w[i] >= mod) w[i] %= mod;curr = (curr * w[i]) % mod;if(curr < 0) curr += mod;}return curr;}

Measured memory_bytes: 5212
#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 3555
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(register int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifndef NTFOrz
		cout<<(clock()-t)/1000.0<<'\n';
		#endif
	}
	ll mod;
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll ksm(ll x,int y,ll mod){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n;

ll fac[sz],_fac[sz];
void init(){fac[0]=_fac[0]=1;rep(i,1,sz-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);}
ll C(int n,int m){return n>=m&&m>=0?fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;}

ll S[sz][sz],Ssum[sz][sz];
ll F[sz][sz],Fsum[sz][sz];

ll pw2[sz];
namespace SHIT
{
	#define S 32768
	ll pw1[S],pw2[S];
	void init()
	{
		pw1[0]=1;rep(i,1,S-1) pw1[i]=pw1[i-1]*2%mod;
		pw2[0]=1;pw2[1]=pw1[S-1]*2%mod;rep(i,2,S-1) pw2[i]=pw2[i-1]*pw2[1]%mod;
	}
	ll ksm(int x){return pw2[x>>15]*pw1[x&32767]%mod;}
	#undef S
}

int main()
{
	file();
	read(n,mod);
	init();SHIT::init();
	S[0][0]=1;rep(i,1,n) rep(j,1,i) (S[i][j]+=S[i-1][j-1]+S[i-1][j]*j%mod)%=mod;
	rep(i,0,n) rep(j,1,n) (Ssum[i][j]=Ssum[i][j-1]+S[i][j])%=mod;
	rep(p,0,n) rep(i,0,n) (F[0][p]+=S[i][0]*C(p,i)%mod)%=mod;
	Fsum[0][0]=F[0][0];rep(p,1,n) Fsum[0][p]=(Fsum[0][p-1]+F[0][p])%mod;
	rep(m,1,n) rep(i,0,n) (F[m][0]+=S[i][m]*C(0,i)%mod)%=mod,Fsum[m][0]=F[m][0];
	rep(m,1,n) rep(p,1,n) (F[m][p]=Fsum[m][p-1]*m%mod+Fsum[m-1][p-1])%=mod,Fsum[m][p]=(Fsum[m][p-1]+F[m][p])%mod;
	pw2[0]=1;rep(i,1,n) pw2[i]=pw2[i-1]*2%(mod-1);
	ll ans=0;
	rep(k,0,n)
		rep(l,0,n)
			(ans+=F[l][n-k]*(((n+k)&1)?mod-1:1ll)%mod*SHIT::ksm((k*l+pw2[k])%(mod-1))%mod*C(n,k)%mod)%=mod;
	cout<<ans;
	return 0;
}

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

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

class DisjointSet{
    public:
        vector<ll> rank,p,siz;

        DisjointSet(){}
        DisjointSet(ll size){
            rank.resize(size,0);
            p.resize(size,0);
            siz.resize(size,1);
            rep(i,size) makeSet(i);
        }

        void makeSet(ll x){
            p[x] = x;
            rank[x] = 0;
        }

        bool same(ll x, ll y){
            return root(x) == root(y);
        }

    
        void unite(ll x, ll y){
            x = root(x);
            y = root(y);
            if(rank[x] > rank[y]){
                siz[x] += siz[y];
                p[y] = x;
            }
            else{
                siz[y] += siz[x];
                p[x] = y;
                if(rank[x] == rank[y]) rank[y]++;
            } 
        }
        ll root(ll x){
            if(x != p[x]){
                p[x] = root(p[x]);
            }
            return p[x];
        }

        ll size(ll x){
            return siz[root(x)];
        }

};



int main(){
  ll N,M; cin >> N >> M;
  vector<ll> A(M),B(M);
  rep(i,M){
    cin >> A[i] >> B[i];
    A[i]--; B[i]--;
  }
  DisjointSet Unko(N);
  vector<ll> inc(M);

  inc[M-1] = N * (N-1) / 2;
  for(int i = M-1; i >= 1; i--){
      if(Unko.same(A[i],B[i])){
          inc[i-1] = inc[i];
      }
      else{
        inc[i-1] = inc[i] - (Unko.size(A[i]) * Unko.size(B[i]));
        Unko.unite(A[i],B[i]);
      }
  }

  rep(i,M){
      cout << inc[i] << endl;
  }

}


Measured memory_bytes: 6016
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define yn(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YN(ans) if(ans)printf("YES\n");else printf("NO\n")
#define vector1d(type,name,...) vector<type>name(__VA_ARGS__)
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
ll updivide(ll a,ll b){if(a%b==0) return a/b;else return (a/b)+1;}

int main(){
    string s,t;
    cin>>s;
    char c='a';
    int ans=1000,d=0;
    set<char> kind;
    rep(i,s.length())kind.insert(s[i]);
    for(auto key:kind){
        t=s;
        d=0;
        while(count(all(t),key)!=t.length()){
            d++;
            for(int i=t.length()-1;i>=0;i--){
                if(t[i]!=key){
                    t.erase(t.begin()+i);
                    for(int j=0;j<i;j++){
                        if(j+1<i&&t[j+1]==key){
                            t[j]=key;
                        }
                    }
                    goto skip;
                }
            }
            skip: ;
            //debug(t);
        }
        ans=min(ans,d);
    }
    out(ans);
}

Measured memory_bytes: 3724
import java.util.*;
public class Main
{
  public static void main(String args[])
  {
    Scanner sc=new Scanner(System.in);
    int arr[][]=new int[3][3];
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            arr[i][j]=sc.nextInt();
        }
    }
    int n=sc.nextInt();
    boolean vis[][]=new boolean[3][3];
    for(int x=0;x<n;x++)
    {
        int t=sc.nextInt();
        outer:for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                if(t==arr[i][j])
                {
                    vis[i][j]=true;
                    break outer;
                }
            }
        }
    }
    for(int i=0;i<3;i++)
    {
        int cntr=0;
        for(int j=0;j<3;j++)
        {
            if(vis[i][j])
            cntr++;
        }
        if(cntr==3)
        {
            System.out.println("Yes");
            return;
        }
    }
    for(int i=0;i<3;i++)
    {
        int cntr=0;
        for(int j=0;j<3;j++)
        {
            if(vis[j][i])
            cntr++;
        }
        if(cntr==3)
        {
            System.out.println("Yes");
            return;
        }
    }
    if((vis[0][0]&&vis[1][1]&&vis[2][2])||(vis[1][1]&&vis[0][2]&&vis[2][0]))
    {
        System.out.println("Yes");
        return;
    }
    System.out.println("No");
  }
}


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

int main()
{
  int w;
  int ans;

  while(1){
    cin >> w;
    if(w == -1) break;

    ans = 0;
    if(w > 30){
      ans += (w - 30) * 160;
      w = 30;
    }
    if(w > 20){
      ans += (w - 20) * 140;
      w = 20;
    }
    if(w > 10){
      ans += (w - 10) * 125;
      w = 10;
    }
    ans += 1150;

    cout << 4280 - ans << endl;
  }

  return 0;
}



Measured memory_bytes: 3100
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>

using namespace std;

#define	numberof(a)	(sizeof(a) / sizeof(a[0]))
#define	INF		(1000000)
#define Rep(i,n) for(int i = 0; i < (n); i++ )

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define	show(x)	 copy( (x).begin(), (x).end(), ostream_iterator<int>(cout, ",") );	// container<int>を全て表示

using namespace std;

typedef long long ll;

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main()
{
	ll N = 0;
	ll ans = 0;
	ll numOfOnePair = 0;
	ll numOfTwoPair = 0;
	map<ll, ll> A;
	map<ll, ll>::iterator itr;

	cin >> N;

	Rep(i, N) {
		ll tmp = 0;
		cin >> tmp;
		A[tmp]++;
		if (A[tmp] % 2 == 0) {
			A[tmp] = 2;
		}
		else{
			A[tmp] = 1;
		}
	}

	for (itr = A.begin(); itr != A.end(); itr++ ) {
		if (itr->second == 2) {
			numOfTwoPair++;
		}
		else {
			numOfOnePair++;
		}
	}

	ans = numOfOnePair;
	if (numOfTwoPair % 2 == 0 ) {
		ans += numOfTwoPair;
	}
	else {
		ans += (numOfTwoPair - 1);
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 6528
// Problem : A - Sheep and Wolves
// Contest : AtCoder - AtCoder Beginner Contest 164
// URL : https://atcoder.jp/contests/abc164/tasks/abc164_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
#include <unordered_map>
#define int long long int
#define double long double
#define endl "\n"
#define PI 3.141592653589793238462643383279502884
#define sp(x)   setprecision(x)
#define ceil(a,b)   (a+(b-1))/b
#define LCM(a,b)    (a*b)/__gcd(a,b)
#define all(v)  v.begin(),v.end()
#define alls(s,v)  s.begin(),s.end(),v
#define gena(arr,n,nxt)  generate(arr,arr+n, nxt)
#define genv(v,nxt)  generate(v.begin(),v.end(), nxt)
#define base ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define exit return 0;
using namespace std;
const int N=1000000;
bool prime[N];
void sieve(){memset(prime, true, sizeof(prime));for (int p=2; p*p<100000000; p++)
{if (prime[p] == true){for (int i=p*p; i<100000; i += p)prime[i] = false;}}}
int power(int x, int y){int res = 1;while (y > 0){if (y & 1)res = res * x;y = y >> 1;x = x*x;}return res;}
int nxt(){int x;cin >> x;return x;}
vector<int>adj[N];
bool vis[N];
vector<int>order;
void dfs(int u){
    vis[u]=1;
    for(auto v:adj[u])if(!vis[v])dfs(v);
    order.push_back(u);
}
int32_t main(){
    base
    int n=nxt(),m=nxt();
    cout<<(m>=n?"unsafe":"safe");
    exit
}


Measured memory_bytes: 27084
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int h,w;
  cin >> h >> w;
  vvi field(h, vi(w, 0));
  rep(y, h){
    rep(x, w){
      char s;
      cin >> s;
      if(s == '#') field[y][x] = 1;
    }
  }
  int movex[] = {0, 0, 1, -1};
  int movey[] = {1, -1, 0, 0};
  rep(y, h){
    rep(x, w){
      if(field[y][x]){
        bool ok = false;
        rep(i, 4){
          int posx = movex[i] + x;
          int posy = movey[i] + y;
          if(posx >= 0 && posx < w && posy >= 0 && posy < h && field[posy][posx]){
            ok = true;
            break;
          }
        }
        if(!ok){
          cout << "No" << endl;
          return 0;
        }
      }
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
signed int A,B;
 signed int sum,diff,mul;
  cin>>A>>B;
  sum=A+B;
  
  diff=A-B;
  mul=A*B;
  int maxx;
  maxx=max(sum,max(diff,mul));
  
  cout<<maxx<<endl;
  
  
 return 0; 
}

Measured memory_bytes: 256