akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

signed main() {
	int x, y; double cnt(0);
	int sum(0); char c; int n(0);
	while (cin >> x >> c >> y) {
		sum += x*y;
		n += y;
		cnt++;
	}
	cout << sum << endl;
	cout << (int)round(n / cnt) << endl;
	return 0;
}

Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
int i,n,m,ch[100005][2],p,tot,j,ed[100005];
long long k,ans;
char c[100005];
long long lowbit(long long x)
{
	return -x&x;
}
void dfs(int i,int j)
{
	if(ed[i]==1)
		return;
	if(i==0)
	{
		ans^=lowbit(k-j+1);
		return;
	}
	dfs(ch[i][0],j+1);
	dfs(ch[i][1],j+1);
}
int main()
{
	scanf("%d %lld",&n,&k);
	tot=1;
	for(i=1;i<=n;++i)
	{
		scanf("%s",c);
		p=1;
		for(j=0;c[j];++j)
		{
			if(!ch[p][c[j]-'0'])
				ch[p][c[j]-'0']=++tot;
			p=ch[p][c[j]-'0'];
		}
		ed[p]=1;
	}
	dfs(1,0);
	puts(ans?"Alice":"Bob");
}


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

using namespace std;

int main(){
	int k, t, ans = 0;
	cin >> k >> t;
    vector<int> a(t);
    for(int i = 0; i < t; i++){
        cin >> a[i];
    }
    int m = *max_element(begin(a), end(a));
    ans = max(0, m - (k - m) - 1);
	cout << ans << endl;
	return 0;
}

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

// Begin {{{
using namespace std;
#define all(x) x.begin(), x.end()
#define rep(i, n) for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, b, e) for (i64 i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (i64 i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<>>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
inline i64 sigma(i64 n) { return n * (1 + n) >> 1; }
inline i64 updiv(i64 n, i64 d) { return (n + d - 1) / d; }
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;
#ifndef DEBUG
#define dump(...)
#endif

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}

inline void outs() { cout << "\n"; }
template <class Head, class... Tail>
inline void outs(Head&& head, Tail&&... tail) {
    cout << head << (sizeof...(tail) ? " " : "");
    outs(forward<Tail>(tail)...);
}

template <class T>
inline void outs(vector<T> &vec) { for (auto &e : vec) cout << e << " \n"[&e == &vec.back()]; }

template <class T>
inline void outs(vector<vector<T>> &df) { for (auto &vec : df) outs(vec); }

inline void outl() { cout << "\n"; }
template <class Head, class... Tail>
inline void outl(Head&& head, Tail&&... tail) {
    cout << head << (sizeof...(tail) ? "\n" : "");
    outl(forward<Tail>(tail)...);
}

template <class T>
inline void outl(vector<T> &vec) { for (auto &e : vec) cout << e << "\n"; }

inline void outn() {}
template <class Head, class... Tail>
inline void outn(Head&& head, Tail&&... tail) {
    cout << head;
    outn(forward<Tail>(tail)...);
}

template <class T>
inline void outn(vector<T> &vec) { for (auto &e : vec) cout << e; }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
    return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}
// }}} End

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

    var(int, N, M);

    vector<pii> vec;
    rep(i, N) {
        var(int, a, b);
        vec.emplace_back(a, b);
    }

    sort(all(vec));

    i64 res = 0;
    i64 cnt = 0;
    rep(i, N) {
        i64 loop = vec[i].second;
        while (loop--) {
            res += vec[i].first;
            ++cnt;
            if (cnt >= M) {
                outl(res);
                return 0;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 2420
import sys
import bisect
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce


def permutation(n, r):
    if r == 0:
        return 1
    else:
        return reduce(mul, range(n, n - r, -1))


def combination(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(1, r + 1))


def fermat_s_little_theorem(denominator_no, molecule_no1, molecule_no2, mod):
    denominator = 1
    for i in range(1, denominator_no + 1):
        denominator = (denominator * i) % mod
    molecule = 1
    for i in range(1, molecule_no1 + 1):
        molecule = (molecule * i) % mod
    for i in range(1, molecule_no2 + 1):
        molecule = (molecule * i) % mod
    return denominator * pow(molecule, mod - 2, mod) % mod


def slove():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    for i in range(1, k + 1):
        if k - 1 >= i - 1 and n - k + 1 >= i:
            print(combination(n - k + 1, i) % mod * combination(k-1, i-1) % mod)
        else:
            print(0)


if __name__ == '__main__':
    slove()


Measured memory_bytes: 70232
#include <iostream>

using namespace std;

#define MAX 10

struct P{
  int x,y;
};

int n;
P sp[MAX];
const int px[12] = {-2,-2,-2,-1,-1,0,0,1,1,2,2,2};
const int py[12] = {-1,0,1,-2,2,-2,2,-2,2,-1,0,1};
const int dx[9] = {1,1,1,-1,-1,-1,0,0,0};
const int dy[9] = {-1,0,1,-1,0,1,-1,0,1};

bool check(int x,int y){
  if(x < 0 || y < 0 || x > 9 || y > 9){
    return false;
  }

  return true;
}

bool solve(int x,int y,int s){
  if(s == n){
    return true;
  }

  for(int i = 0 ; i < 12 ; i++){
    int nx = x + px[i];
    int ny = y + py[i];

    if(!check(nx,ny)) continue;
    
    for(int j = 0 ; j < 9 ; j++){
      int spx = sp[s].x + dx[j];
      int spy = sp[s].y + dy[j];
    
      if(!check(spx,spy)) continue;

      if(nx == spx && ny == spy){
	if(solve(nx,ny,s+1)){
	  return true;
	}
      }
    }
  }  

  return false;
}

int main(){
  int sx,sy;
  while(cin >> sx >> sy ,(sx | sy)){
    cin >> n;
    for(int i = 0 ; i < n ; i++){
      cin >> sp[i].y >> sp[i].x;
    }
    if(solve(sy,sx,0)){
      cout << "OK" << endl;
    }else{
      cout << "NA" << endl;
    }
  } 

  return 0;
}

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

int swap(int &a,int &b)
{
    int t = a;
    a = b;
    b = t;
}
int main() {
    int r,s,t;
    cin>>r>>s>>t;
    if (r>s) swap(r,s);
    if (r>t) swap(r,t);
    if (s>t) swap(s,t);
    cout<<r<<' '<<s<<' '<<t<<endl;
    return 0;
}


Measured memory_bytes: 3072
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;
int main()
{int n,x;
 cin>>n>>x;
    while(n!=0||x!=0){
    
        int ans=0;
 int a,b,c;
 for(a=1;a<n+1;a++){
     for(b=a+1;b<n+1;b++){
       c=x-a-b;
         if(c>b&&c<n+1){
         ans++;
         }
     }
 }
 cout<<ans<<endl;
        cin>>n>>x;
    }
}
// GCC reference:
//   https://gcc.gnu.org/

// C++ language references:
//   https://cppreference.com/
//   https://isocpp.org/
//   http://www.open-std.org/jtc1/sc22/wg21/

// Boost libraries references:
//   https://www.boost.org/doc/





Measured memory_bytes: 3084
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n,k,i,cnt=0;
  cin >> n >> k;
  vector<int>d(k),ans(n,0);
  for(i=0; i<k; i++){
    cin >> d.at(i);
    vector<int>a(n);
    for(int j=0; j<d.at(i); j++){
      cin >> a.at(j);
      ans.at(a.at(j)-1)++;
    }
  }
  for(i=0; i<n; i++){
    if(ans.at(i)==0){
      cnt++;
    }
  }
  cout << cnt << endl;
}


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

int main() {
  int a, b;
  cin >> a >> b;
  for(int i=1; i<15000; i++) {
    int temp1 = i*0.08;
    int temp2 = i*0.1;
    if(temp1 == a && temp2 == b) {
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll linf = (1LL << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int n;
struct edge { int to, cost; };
vector<edge> g[100005];
int d[100005];
vector<int> path;
map<int, bool> vi;
bool ng;

void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P>> que;
	fill(d, d + n, inf);
	d[s] = 0;
	que.push(P(0, s));
	map<int, int> mp;
	mp[s] = -1;
	while (que.size()) {
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (auto& c : g[v]) {
			edge e = c;
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
				mp[e.to] = v;
			}
		}
	}
	//////////////////以下構築
	for (int i = n - 1; i >= 1; --i) {
		if (d[i] == inf) {
			ng = true;
			break;
		}
		int pos = i;
		path.emplace_back(mp[pos]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m;
	cin >> n >> m;
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(edge{ b, 1 });
		g[b].push_back(edge{ a, 1 });
	}
	ng = false;
	dijkstra(0);
	if (ng) cout << "No" << endl;
	else {
		reverse(all(path));
		cout << "Yes" << endl;
		rep(i, path.size()) {
			cout << path[i] + 1 << endl;
		}
	}
	return 0;
}

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

int main()
{
    int n,sum=0,ttl=0;
    cin>>n;
    int v[n];
    for(int i=0; i<n ;i++){
        cin>>v[i];
        sum+=v[i];
    }
    int minn=10000000;
    for(int i=-100; i<=100; i++){
        for(int j=0; j<n; j++){
            ttl+=((v[j]-i)*(v[j]-i));
        }
        if(ttl<minn)
            minn=ttl;
        ttl=0;
    }
    cout<<minn;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

int main(){
	string s;
	cin >> s;

	string sr = s;
	reverse(all(sr));
	string t;
	for(auto i : sr){
		if(i == 'b'){
			t += 'd';
		}else if(i == 'd'){
			t += 'b';
		}else if(i == 'p'){
			t += 'q';
		}else if(i == 'q'){
			t += 'p';
		}else{
			t += i;
		}
	}

	cout << (s == t ? "Yes" : "No") << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	int n, c;
	cin >> n >> c;
	int d[c][c];
	for (int i = 0; i < c; i++)
		for (int j = 0; j < c; j++)
			cin >> d[i][j];
	map<int, int> m0;
	map<int, int> m1;
	map<int, int> m2;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int col;
			cin >> col;
			if ((i+1+j+1)%3 == 0) {
				m0[col]++;
			} else if ((i+1+j+1)%3 == 1) {
				m1[col]++;
			} else {
				m2[col]++;
			}
		}
	}

	long long ans = -1;
	for (int i = 0; i < c; i++) {
		for (int j = 0; j < c; j++) {
			if (i == j)
				continue;
			for (int k = 0; k < c; k++) {
				if (i == k || j == k)
					continue;
				long long count = 0;
				for (auto e : m0) {
					count += (long long)(d[e.first-1][i])*(long long)(e.second);
				}
				for (auto e : m1) {
					count += (long long)(d[e.first-1][j])*(long long)(e.second);
				}
				for (auto e : m2) {
					count += (long long)(d[e.first-1][k])*(long long)(e.second);
				}
				if (ans == -1)
					ans = count;
				else
					ans = min(ans, count);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int gcd(int x, int y, int z) {
	int  d, i;
	d = 1;
	i = 1;
	while ( i <= x && i <= y && i <= z) {
		if (x % i == 0 && y % i == 0 && z % i == 0)
			d = i;
		i++;
	}
	return d;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int k, sum = 0;
	cin >> k;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			for (int m = 1; m <= k; m++) {
				sum += gcd(i, j, m);
			}
		}
	}
	cout << sum << endl;
}



Measured memory_bytes: 3596
#include <algorithm>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define eps LDBL_EPSILON
#define mod 1000000007
#define double long double
#define INF INT_MAX
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int n, x[60], y[60];
signed main() {
	cin >> n;
	rep(i, n)cin >> x[i] >> y[i];
	int ans = INF;
	rep(i, n) {
		rep(j, n) {
			if (i == j)continue;
			int p = x[i] - x[j], q = y[i] - y[j], cnt = 0;
			rep(k, n) {
				bool f = true;
				rep(l, n) {
					if (p == x[k] - x[l] && q == y[k] - y[l])f = false;
				}
				if (f)cnt++;
			}
			ans = min(ans, cnt);
		}
	}
	if (n >= 2)cout << ans << endl;
	else cout << 1 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, A, B, C, D;
char In[200020];

void NO() { puts("No"); exit(0); }

int main() {
	scanf("%d%d%d%d%d", &N, &A, &B, &C, &D);
	scanf("%s", In+1);
	if(A > C || B > D) {
		NO();
	}
	if(A > B) swap(A, B), swap(C, D);
	for(int i=A+1;i<=C;i++) if(In[i] == '#' && In[i-1] == '#') NO();
	for(int i=B+1;i<=D;i++) if(In[i] == '#' && In[i-1] == '#') NO();
	if(D < C) {
		int ok = 0;
		for(int i=B;i<=D;i++) if(In[i] != '#' && In[i-1] != '#' && In[i+1] != '#') ok = 1;
		if(!ok) NO();
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main() {
    int n, k; cin >> n >> k;
    vector<ll> x(n);
    rep(i, n) {
        cin >> x[i];
    }
    auto it = lower_bound(x.begin(),x.end(),0);
    int left = it - x.begin();
    int right = n - left;
    ll mi = 1e18;
    for(int i=0; i<=left&&i<=k; i++) {//左i個
        ll length = 0LL;
        if(k-i > right) continue;
        //printf("right:%d\n",left+k-i-1);
        if(i == 0) length = x[left + k - i -1];
        else if(i == k) length = -x[left - i];
        else {
            if(abs(x[left - i]) < abs(x[left + k - i -1]))
                length = 2LL*abs(x[left - i]) + abs(x[left + k - i -1]);
            else
                length = 2LL*abs(x[left + k - i -1]) + abs(x[left - i]);
        }
        mi = min(mi, length);
    }
    cout << mi;
}


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

const double eps = 1e-9;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define FORD(i,a,b) for (int i = int(b)-1; i >= (a); i--)
#define FORIT(i,c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define mp make_pair
#define pb push_back

int p[200200];


int rmq_[20][200200];

pii rmq(int f, int t){
//    cout << "rmq(" << f<< " " <<t << ")=";
    assert((t - f) % 2 == 0);
    int p = 0;
    while(f + (1<< (p+1)) <= t)++p;
    assert(f + (1 << p) <= t);
    assert(f + (1 << (p+1)) > t);
    int f2 = t - (1 << p);
    if(rmq_[p-1][f2] < rmq_[p-1][f]){
        f = f2;
    }
    while(--p > 0){
        if(rmq_[p][f] != rmq_[p-1][f])f += (1<<p);
    }
//    cout << rmq_[0][f] << "," << f << endl;
    return mp(rmq_[0][f], f);
}

int main(){
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    FOR(i,0,N)cin >> rmq_[0][i];
    FOR(p,1,20){
        int step = 1<<(p);
        FOR(i,0,N){
            rmq_[p][i] = rmq_[p-1][i];
            if(i+step < N)rmq_[p][i] = min(rmq_[p][i], rmq_[p-1][i+step]);
        }
    }
    /*
    FOR(p,0,4){
        FOR(n,0,N)cout << rmq_[p][n] << " ";
        cout << endl;
    }
    cout << endl;*/
    set<pair<pii,pii > > pq;
    pq.insert(mp(rmq(0,N),mp(0,N)));
    bool first = true;
    while(!pq.empty()){
        auto b = pq.begin();
        int F = b->second.first, T = b->second.second;
        assert((T - F) % 2 == 0);
        int v = b->first.first, pos = b->first.second;
        auto b2 = rmq(pos + 1, T + 1);
        int v2 = b2.first;
        int pos2 = b2.second;
        assert(pos2 > pos);
        assert(pos2 < T);
        if(first)first = false;
        else cout << " ";
        cout << v << " " << v2;
        pq.erase(b);
        assert(pos >= F);
        assert(pos2 > pos);
        if(pos != F){
            pq.insert(mp(rmq(F, pos), mp(F,pos)));
        }
        if(pos + 1 != pos2){
            pq.insert(mp(rmq(pos+1,pos2), mp(pos+1, pos2)));
        }
        if(pos2 + 1 != T){
            pq.insert(mp(rmq(pos2+1, T), mp(pos2+1, T)));
        }
    }
    cout << endl;

	return 0;
}

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

int main() {
int N,K,sum;
sum=0;
cin>>N>>K;
for(int i = 0;i<N;i++){
int x;
cin>>x;
if(x>K/2){
 if(x>=K){
sum+=(x-K)*2;}
else {sum +=(K-x)*2;}
}
else{sum+=x*2;}
}
cout<<sum;
}


Measured memory_bytes: 3600
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val N, M = sc.nextInt()
    val G = Array.fill(N)(Nil: List[Int])
    for (_ <- 0 until M) {
      val u, v = sc.nextInt()
      G(u - 1) ::= (v - 1)
    }

    def solve(N: Int, M: Int, G: Array[List[Int]]): Boolean = {
      val visit = new Array[Boolean](N)
      def dfs(stack: List[(Int, Int)]): Boolean =
        if (stack.nonEmpty) {
          val (depth, u) = stack.head
          if (depth <= 2) {
            if (u == N - 1) {
              true
            } else if (!visit(u)) {
              visit(u) = true
              dfs(
                G(u).foldLeft(stack.tail)(
                  (stack, v) => (depth + 1, v) :: stack))
            } else {
              dfs(stack.tail)
            }
          } else {
            dfs(stack.tail)
          }
        } else {
          false
        }
      dfs((0, 0) :: Nil)
    }

    println(if (solve(N, M, G)) "POSSIBLE" else "IMPOSSIBLE")
  }

}


Measured memory_bytes: 120892
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

using P = pair<int, int>;

static const long long MOD = 1000000007;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;

int dist[105][105];
int A[1005], B[1005], C[1005];
int ans;

int main(void) {
  int n, m;
  cin >> n >> m;
  rep(i, 0, 105) rep(j, 0, 105) {
    if (i==j) dist[i][j] = 0;
    else dist[i][j] = INF;
  }
  rep(i, 0, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    dist[a][b] = dist[b][a] = c;
    A[i] = a;
    B[i] = b;
    C[i] = c;
  }

  for (int k=0; k<n; k++) {
    for (int i=0; i<n; i++) {
      for (int j=0; j<n; j++) {
        dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
      }
    }
  }

  for (int k=0; k<m; k++) {
    bool flag = false;
    int a = A[k], b = B[k], c = C[k];
    for (int i=0; i<n; i++) {
      for (int j=0; j<n; j++) {
        if (dist[i][j]==dist[i][a]+dist[b][j]+c || dist[i][j]==dist[i][b]+dist[a][j]+c) flag = true;
      }
    }
    if (!flag) ans++;
  }
  

  
  cout << ans << endl;

    return 0;
}



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

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> vs(n);
    vector<int> cs(n);
    for (auto& v : vs)
    {
        cin >> v;
    }
    for (auto& c : cs)
    {
        cin >> c;
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (vs[i] - cs[i] > 0)
        {
            ans += vs[i] - cs[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

long odd(long num) { return (num - num % 2) / 2; }
int main() {

  using namespace std;
  string S, S2;
  long K;
  cin >> S;
  cin >> K;
  vector<long> L;
  S2 = S + S.at(0);

  long count = 1;
  for (long i = 0; i < S2.size(); i++) {
    if (i + 1 == S2.size() || S2.at(i) != S2.at(i + 1)) {
      L.push_back(count);
      count = 1;
    } else {
      count++;
    }
  }

  long result = 0;
  if (L.size() != 1) {
    result += odd(L[0]);
    result += odd(L[L.size() - 1] - 1);
    if (*(L.end()) != 1) {
      result += odd(L[0] + L[L.size() - 1] - 1) * (K - 1);
    } else {
      result += (odd(L[0]) + odd(L[L.size() - 1])) * (K - 1);
    }
    for (long i = 1; i < L.size() - 1; i++) {
      result += odd(L[i]) * K;
    }
  } else {
    result += odd(K * (L[0] - 1));
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 256
l, r = gets.split.map(&:to_i)

ans = 2018
zero_divided = false

l.upto(r - 1) do |i|
  if zero_divided
    ans = 0
    break
  end

  (i + 1).upto(r) do |j|
    p = i * j % 2019

    if p == 0
      zero_divided = true
      break
    end

    ans = p if p <= ans
  end
end

puts ans


Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <iomanip>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define ANTHRO(x...) cerr << "[" << #x << "] = [", _print(x)
#else
#define ANTHRO(x...)
#endif


#define ll long long
#define MOD 1000000007
#define INF (int)1e9
#define EPS 1e-9
/*
    This is I-Coins from AtCoder
*/

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n; cin>>n;
    vector<long double> dp(n+1,0);
    dp[0]=1;
    long double an=0;
    for(ll i=0;i<n;i++){
        long double x; cin>>x;
        for(ll j=i+1;j>=0;j--){
            dp[j]=((j==0)?0:dp[j-1]*x)+dp[j]*(1-x);
        }
        //an+=dp[i];
    }
    //cout<<dp<<"\n";
    //ANTHRO(dp);
    for(ll i=n;i>(n-i);i--){
        //ANTHRO(i,n-i);
        an+=dp[i];
    }
    cout<<setprecision(10)<<an<<"\n";
    return 0;
}



Measured memory_bytes: 384
//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include<bits/stdc++.h>
using namespace std;

#define all(a) begin(a),end(a)
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}

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

int sub(int a,int b){
  a-=b;
  if(a<0){
    a+=mod;
  }
  return a;
}

int powz(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=mul(res,a);
    }
    b/=2;
    a=mul(a,a);
  }
  return res;
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}

template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}

template<typename T>
vector<pair<T,int>> getvec(int n){
  vector<pair<T,int>>a(n);
  for(int i=0;i<a.size();i++){
    cin>>a[i].F;
    a[i].S=i;
  }
  return a;
}

void clr(auto &a,int n){
  a.clear();
  a.resize(n);
}

void unq(auto &a){
  sort(all(a));
  a.resize(unique(all(a))-a.begin());
}

const int N=300005;

void solve(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  int op=0;
  vector<int>a(2*n);
  for(int i=0;i<2*n;i++){
    if(s[i]=='W'){
      if(op){
	a[i]=1;
      }
      else{
	a[i]=2;
      }
      op^=1;
    }
    else{
      if(op){
	a[i]=2;
      }
      else{
	a[i]=1;
      }
      op^=1;
    }
  }
  int ans=1,tot=0;
  for(int i=0;i<2*n;i++){
    tot+=(a[i]==2);
  }
  if(tot!=n){
    cout<<0;
    return;
  }
  reverse(all(a));
  tot=0;
  for(int i=0;i<2*n;i++){
    if(a[i]==2){
      tot++;
      continue;
    }
    ans=mul(ans,tot);
    tot--;
  }
  debug(a);
  int fc=1;
  for(int i=2;i<=n;i++){
    fc=mul(fc,i);
  }
  cout<<mul(ans,fc);
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //cin>>tc;
  for(int _=0;_<tc;_++){
    // cout<<"Case #"<<_+1<<": ";
    solve();
    if(_!=tc-1){
      cout<<'\n';
    }
  }
}



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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<double> value(n);
    for (int i = 0; i < n; ++i) {
        cin >> value.at(i);
    }
    sort(value.begin(), value.end());
    reverse(value.begin(), value.end());
    double amount = 0;
    for (int j = 0; j < n - 1; ++j) {
        amount += value.at(j) / pow(2, j + 1);
    }
    amount += value.at(n - 1) / pow(2, n - 1);
    cout << amount << endl;
}


Measured memory_bytes: 256
n=int(input())
now=[0,0,0]#t,x,y
f=True
for i in range(n):
    t,x,y=map(int,input().split())
    k=abs(x-now[1])+abs(y-now[2])
    l=abs(t-now[0])
    if not(k<=l and abs(k-l)%2==0):
        f=False
    now=[t,x,y]
print("Yes" if f else "No")

Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fast_input() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}


int solve(int N){
    int const INF = 10000000;
    int ret = 0;
    vector<string> airports(N);
    vector<string> parsed(N);
    for (int i = 0; i < N; i++) {
        cin >> airports[i];
    }
    char vowel[] = {'a', 'i', 'u', 'e', 'o'};
    for (int i = 0; i < N; i++) {
        string p;
        for (int k = 0; k < airports[i].length(); k++) {
            for (int j = 0; j < 5; j++) {
                if (k == 0 || airports[i][k-1] == vowel[j]) {
                    p.push_back(airports[i][k]);
                    break;
                }
            }
        }
        parsed[i] = p;
    }

    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            int len = 0;
            for (int k = 0; k < parsed[i].length() && k < parsed[j].length(); k++) {
                len = k+1;
                if (parsed[i][k] != parsed[j][k]) {
                    break;
                }
                if (k == parsed[i].length() - 1 || k == parsed[j].length() - 1) {
                    if (parsed[i].length() != parsed[j].length()) {
                        len = k+2;
                    } else {
                        len = INF;
                    }
                }
            }
            ret = max(len, ret);
        }
    }
    if (ret == INF) ret = -1;
    return ret;
}

int main(void) {
    int N;
    vector<int> ans;
    while (1) {
        cin >> N;
        if (!N) break;
        ans.push_back(solve(N));
    }
    for (int &i : ans) {
        cout << i << endl;
    }
    return 0;
}   



Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vector<vector<vector<int>>> building;
    building.resize(4);
    for(size_t i=0; i<4; i++){
        building[i].resize(3);
        for(size_t j=0; j<3; j++){
            building[i][j].resize(10);
        }
    }
    for(int i=0; i<n; i++){
        int b,f,r,v;
        cin>>b>>f>>r>>v;
        building[b-1][f-1][r-1]+=v;
    }
    for(int i=0; i<4; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<10; k++){
                cout<<" "<<building[i][j][k];
            }
            cout<<endl;
        }
        if(i<3) cout<<"####################"<<endl;
        if(i==4) cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3236
#include<stdio.h>
int main() {
	int a, b = 0;
	scanf("%d", &a);
	int c = 100;
	for (int i = 0; i < 3; i++) {
		if (a / c == 1) { 
			b++;
			a -= c;
		}
		c = c / 10;
	}
	printf("%d", b);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
using namespace std;
using ll = long long;
int main(){
    ll n,m,a;
    ll NUM = 1e9+7;
    cin >> n >> m;
    vector<ll> vc(n+1);
    for(ll i=0;i<m;i++){
         cin >> a;
         vc[a]=-1;
    }
    if(vc[1]!=-1)   vc[1]=1;
    if(vc[2]!=-1){
        vc[2]=1;
        if(vc[1]>0) vc[2]++;
    }
    for(ll i=3;i<=n;i++){
        if(vc[i]==-1)   continue;
        else if(vc[i-2]>0&&vc[i-1]>0)    vc[i] = vc[i-2] + vc[i-1];
        else if(vc[i-2]>0)  vc[i] = vc[i-2];
        else if(vc[i-1]>0)  vc[i] = vc[i-1];
        vc[i]%=NUM;
    }
    cout << vc[n] << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

template<typename T>
struct BIT {
    int n;
    vector<T> d;
    BIT(int n=0):n(n),d(n+1) {}
    void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
        d[i] += x;
    }
    }
    T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
        x += d[i];
    }
    return x;
    }
    T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
    }
};

int main() {
    // Binary Indexed Tree
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    // 一個前の同じ玉の色の箇所へ矢印を書く、ない時は-1
    vector<int> lastSameCol(N+1, -1);
    vector<vector<int>> arrow(N);
    rep(i, N) {
        int prev = lastSameCol[A[i]];
        if (prev != -1) arrow[prev].push_back(i);
        lastSameCol[A[i]] = i;
    }
    vector<vector<P>> queries(N);
    rep(qi, Q) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        queries[l].emplace_back(r, qi);        
    }
    vector<int> ans(Q);
    BIT<int> bit(N);
    for (int i = N-1; i >= 0; i--) {
        for (int x : arrow[i]) {
            bit.add(x, 1);
        }
        for (auto p : queries[i]) {
            int right = p.first, qi = p.second;
            ans[qi] = right - i + 1 - bit.sum(right);
        }
    }
    rep(i, Q) {
        cout << ans[i] << '\n';
    }
    return 0;
}

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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

////////////////////////////////////////////////////////////////////

const int N = 2e5 + 5;

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	string s, t; cin >> s >> t;
	cout << t << s << endl;

	return 0;
}


Measured memory_bytes: 256
from fractions import gcd
def lcm(a,b):
    return a*b/gcd(a,b)
def ge(a,m):
        i, b = 1, a%m
        while b!=1:
            b = (a*b)%m
            i += 1
        return i
while True:
    tmp = map(int, raw_input().split(" "))
    if tmp[1] == 0:
        break
    print reduce(lcm,(ge(a,m) for a,m in zip(tmp[::2],tmp[1::2])))

Measured memory_bytes: 5900
#include<stdio.h>

int main(void)
{
  int h,n,i,j;
  int a[1001],b[1001];
  scanf("%d%d\n",&h,&n);
  for(i=1;i<=n;i++){
    scanf("%d%d\n",&a[i],&b[i]);
  }
  
  int x[10001][1001];
  int m[10001];
  
  for(i=1;i<=h;i++){
    for(j=1;j<=n;j++){
      if(i>a[j]){
        x[i][j]=m[i-a[j]]+b[j];
      }else{
        x[i][j]=b[j];
      }
      if(j==1||m[i]>x[i][j]){
        m[i]=x[i][j];
      }
    }
  }
  
  printf("%d",m[h]);
  
  return 0;
}

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

string s;

int check = 1;

bool calc(int a, int b) {
	if(a + b == 10) {
		s += '+';
		return true;
	}
	if(a - b == 10) {
		s += '-';
		return true;
	}
	if(a * b == 10) {
		s += '*';
		return true;
	}
	return false;
}

bool calc(int a, int b, int c) {
	if(calc(a + b, c)) {
		s += '+';
		check *= 2;
		return true;
	}
	if(calc(a - b, c)) {
		s += '-';
		check *= 2;
		return true;
	}
	if(calc(a * b, c)) {
		s += '*';
		check *= 2;
		return true;
	}
	if(calc(a, b + c)) {
		s += '+';
		check *= 3;
		return true;
	}
	if(calc(a, b - c)) {
		s += '-';
		check *= 3;
		return true;
	}
	if(calc(a, b * c)) {
		s += '*';
		check *= 3;
		return true;
	}
	return false;
}

bool calc(int a, int b, int c, int d) {
	if(calc(a + b, c, d)) {
		s += '+';
		check *= 5;
		return true;
	}
	if(calc(a - b, c, d)) {
		s += '-';
		check *= 5;
		return true;
	}
	if(calc(a * b, c, d)) {
		s += '*';
		check *= 5;
		return true;
	}
	if(calc(a, b + c, d)) {
		s += '+';
		check *= 7;
		return true;
	}
	if(calc(a, b - c, d)) {
		s += '-';
		check *= 7;
		return true;
	}
	if(calc(a, b * c, d)) {
		s += '*';
		check *= 7;
		return true;
	}
	if(calc(a, b, c + d)) {
		s += '+';
		check *= 11;
		return true;
	}
	if(calc(a, b, c - d)) {
		s += '-';
		check *= 11;
		return true;
	}
	if(calc(a, b, c * d)) {
		s += '*';
		check *= 11;
		return true;
	}
	return false;
}

int main(void) {
	int a[4];
	
	while(true) {
		for(int i = 0; i < 4; ++i) {
			cin >> a[i];
		}
		if(a[0] == 0 && a[1] == 0 && a[2] == 0 && a[3] == 0) {
			break;
		}
		
		int ai, aj, ak, al;
		char x, y, z;
		bool flag = false;
		check = 1;
		s = "";
		
		for(int i = 0; i < 4; ++i) {
			for(int j = 0; j < 4; ++j) {
				for(int k = 0; k < 4; ++k) {
					for(int l = 0; l < 4; ++l) {
						if(i != j && i != k && i != l && j != k && j != l && k != l) {
							if(calc(a[i], a[j], a[k], a[l])) {
								flag = true;
								ai = i;
								aj = j;
								ak = k;
								al = l;
							}
						}
						if(flag)   break;
					}
					if(flag)   break;
				}
				if(flag)   break;
			}
			if(flag)   break;
		}
		
		if(flag) {
			switch(check) {
				case 10 : {
					printf("(((%d%c%d)%c%d)%c%d)", a[ai], s[2], a[aj], s[1], a[ak], s[0], a[al]);
					cout << endl;
					break;
				}
				case 14 : {
					printf("((%d%c(%d%c%d))%c%d)", a[ai], s[1], a[aj], s[2], a[ak], s[0], a[al]);
					cout << endl;
					break;
				}
				case 15 : {
					printf("((%d%c%d)%c(%d%c%d))", a[ai], s[2], a[aj], s[0], a[ak], s[1], a[al]);
					cout << endl;
					break;
				}
				case 21 : {
					printf("(%d%c((%d%c%d)%c%d))", a[ai], s[0], a[aj], s[2], a[ak], s[1], a[al]);
					cout << endl;
					break;
				}
				case 22: {
					printf("((%d%c%d)%c(%d%c%d))", a[ai], s[1], a[aj], s[0], a[ak], s[2], a[al]);
					cout << endl;
					break;
				}
				case 33 : {
					printf("(%d%c(%d%c(%d%c%d)))", a[ai], s[0], a[aj], s[1], a[ak], s[2], a[al]);
					cout << endl;
					break;
				}
			}
		} else {
			cout << 0 << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3244
// ~/Remember,remember the 6th of March
 
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double  EPS = 1e-9;
const ll MOD = 1e9 + 7;
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        arr[i]*=-1;
    }
    vector<int>lcs;
    for(int i=0;i<n;i++)
    {
        int ind=upper_bound(lcs.begin(),lcs.end(),arr[i])-lcs.begin();
        if(ind == lcs.size())
            lcs.push_back(arr[i]);
        else
            lcs[ind]=arr[i];
    }
    cout<<lcs.size()<<endl;
    return 0;
}

Measured memory_bytes: 1276
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#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>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
using namespace std;
int n,m,a[3005][3005][2],ans;
int add(int &x,int y){
    x+=y;
    if(x>=orz)x-=orz;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)a[0][i][0]=1;
    a[0][n][1]=1;
    for(int i=0;i<m;++i){
        for(int j=0;j<=n;++j){
            if(j){
                add(a[i+1][j][0],a[i][j][0]);
                add(a[i+1][j-1][0],a[i][j][0]);
                add(a[i+1][j][1],a[i][j][1]);
                add(a[i+1][j-1][1],a[i][j][1]);
            }
            if(j<n){
                add(a[i+1][j][j==(n-1)],a[i][j][0]);
                add(a[i+1][j+1][j==(n-1)],a[i][j][0]);
                add(a[i+1][j][1],a[i][j][1]);
                add(a[i+1][j+1][1],a[i][j][1]);
            }
        }
    }
    for(int i=0;i<=n;++i)add(ans,a[m][i][1]);
    printf("%d\n",ans);
    //system("pause");
    return 0;
}


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

#define FOR(i,l,r) for(int i = (l);i < (r);i++)
#define ALL(x) (x).begin(),(x).end()
template<typename T> void chmax(T& a,const T& b){if(a < b) a = b;}
template<typename T> void chmin(T& a,const T& b){if(b < a) a = b;}
typedef long long ll;

ll H,W;

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

	cin >> W >> H;
	vector<ll> cost_w(W),cost_h(H);
	FOR(i,0,W){
		cin >> cost_w [i];
	}
	FOR(i,0,H){
		cin >> cost_h [i];
	}
	sort(ALL(cost_w),greater<ll>());
	sort(ALL(cost_h),greater<ll>());

	ll x = W + 1,y = H + 1;
	ll ans = 0;
	while(cost_w.empty() == false || cost_h.empty() == false){
		if(cost_w.empty() == false && (cost_h.empty() == true || cost_w.back() <= cost_h.back())){
			ans += cost_w.back() * y;
			x--;
			cost_w.pop_back();
		}
		else{
			ans += cost_h.back() * x;
			y--;
			cost_h.pop_back();
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a))
#define pq priority_queue
using namespace std;
int main () {
	ll a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q;
	scanf("%lld %lld", &a, &b);
	if (a * 2 >= b) {
		printf("%lld\n", b / 2);
	} else {
		c = (b - a * 2) / 4;
		a += c;
		printf("%lld\n", a);
	}
	return 0;
}

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

int main(){
  int n,d,x; cin>>n;
  cin>>d >>x;
  int sum=0;
  for(int i=0;i<n;i++){
    sum++;
    int a; cin>>a;
    sum+=(d-1)/a;
  }
  cout<<sum+x<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
#include <cstdint>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000000000
#define MAX 200001
#define PI 3.141592653589793

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
const ll MOD = 1000000007;

ll RepeatSquaring(ll n, ll p, ll mod){
    if(p == 0) return 1;
    if(p % 2 == 0){
        ll t = RepeatSquaring(n, p/2, mod);
        return t*t;
    }
    else return n * RepeatSquaring(n, p-1, mod);
}

int main(){
    ll N, K;
    cin >> N >> K;
    vector<ll> a(N);
    rep(i,N) cin >> a[i];
    vector<vector<ll>> dp(N+1,vector<ll>(K+1,0));
    rep(i,N) dp[i][0] = 1;
    rep(i,N)rep(j,K-1){
        if(j+1-a[i] < 0) dp[i+1][j+1] += dp[i][j+1];
        else dp[i+1][j+1] += dp[i][j+1] + dp[i][j+1-a[i]];
        dp[i+1][j+1] %= MOD;
    }
    ll sum = RepeatSquaring(2,N,MOD);
    sum--;
    rep(i,K-1){
        sum -= dp[N][i+1];
        if(sum < 0) sum += MOD;
        else sum %= MOD;
    }
    sort(a.begin(),a.end());
    ll left = -1;
    ll right = N;
    while(right-left > 1){
        ll mid = (left + right) / 2;
        int flag = 0;
        rep(i,N+1)rep(j,K+1){
            if(j == 0) dp[i][j] = 1;
            else dp[i][j] = 0;
        }
        rep(i,N)rep(j,K-1){
            if(i == mid){
                flag = 1;
                continue;
            }
            if(j+1-a[i] < 0) dp[i+1-flag][j+1] += dp[i-flag][j+1];
            else dp[i+1-flag][j+1] += dp[i-flag][j+1] + dp[i-flag][j+1-a[i]];
            dp[i+1-flag][j+1] %= MOD;
        }
        ll sum_sub = RepeatSquaring(2,N-1,MOD);
        sum_sub--;
        rep(i,K-1){
            sum_sub -= dp[N-1][i+1];
            if(sum_sub < 0) sum_sub += MOD;
            else sum_sub %= MOD;
        }
        if(sum % MOD == 2*sum_sub % MOD) left = mid;
        else right = mid;
    }
    cout << left + 1 << endl;
}


Measured memory_bytes: 198876
import java.util.Scanner;
public class Main{
    public static void main(String args[]){
	Scanner in = new Scanner(System.in);
	double r = in.nextDouble();
	double area = r*r*Math.PI;
	double length = 2*r*Math.PI;
	    
	System.out.println(String.format("%.5f %.5f",area,length));
    }
}



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

using namespace std;

int main()
{
    long long n,k,q;
    cin>>n>>k>>q;
    int niza[q];
    for(int i=0 ;i<q; i++)
    {
        cin>>niza[i];
    }
    vector<int> v;
    for(int i=0; i<n+1; i++)
    {
        v.push_back(0);
    }
    for(int i=0; i<q; i++)
    {
        v[niza[i]-1]++;
    }
    for(int i=0; i<n; i++)
    {
        if(k-q+v[i]>0)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 1528
#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <numeric>
#include <map>
#include <unordered_map>

#include <type_traits>

using namespace std;
const long long INF = (long long) (1e18)+1;

vector<pair<int, int>> nums;

int main() {
  int n;
  cin >> n;
  unordered_map<int, int> nums;
  for(int i=0; i<n; ++i) {
    int temp;
    cin >> temp;
    nums[temp]++;
  }

  long long ans = 0;
  for (auto num : nums) {
    ans += (num.first * num.second);
  }

  int q;
  cin >> q;
  for (int i=0; i<q; ++i) {
    int b,c;
    cin >> b >> c;
    ans += ((c-b) * nums[b]);

    nums[c]+=nums[b];
    nums[b] = 0;
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 7064
#include <iostream>
#include <cstdio>
using namespace std;
 
typedef long long ll;
ll n, k, s, b;
ll f(ll p) {
	ll j;
	s = 0;
	j = n;
	while (j > 0) {
		s += j % p;
		j /= p;
	}
	return s;
}
int main()
{
	ll i,j;
	cin >> n >> k;
	if (n < k) {
		cout << -1;
		return 0;
	}
	if (n == k) {
		cout << n + 1;
		return 0;
	}
	for (i = 2; i * i <= n; i++) {
		if (f(i) == k) {
			cout << i;
			return 0;
		}
	}
	for (i = 1; i * i <= n - k; i++) {
		if ((n - k) % i == 0 && f((n - k) / i + 1) == k) b = (n - k) / i + 1;
	}
	if (b != 0) cout << b;
	else cout << -1;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {	
	public static void main(String[]args){
		Scanner scan =new Scanner(System.in);
		while(true){
			int x =scan.nextInt();
			int y=scan.nextInt();
		if(x ==0 && y==0){
			break;
		}	
			
		if(x<y){
			System.out.println(x+" "+y);
		}else{
			System.out.println(y+" " +x);
		}
	}
}
}

Measured memory_bytes: 34456