akhauriyash/Code-Regression huggingface dataset:
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int V,E;//頂点数
int d[16][16];
int dp[16][1<<16];//頂点Sを全て巡って頂点iに至る最短経路とする
int main(){
	cin>>V>>E;
	for(int i =0; i <(1<<16);i++){
		for(int j = 0;j <V;j++){
			dp[j][i]=INF;
		}
	}
	for(int i =0;i <V;i++){
		for(int j =0;j <V;j++){
			d[i][j]=INF;
		}
	}
	for(int i =0;i <E;i++){
		int s,t,c;
		cin>>s>>t>>c;
		d[s][t]=c;
	}
	dp[0][1]=0;
	for(int i =0;i <(1<<V);i++){
		for(int j =0;j <V;j++){
			if((i>>j&1)==0)continue;
			for(int k =0;k < V;k++){
				if((i>>k&1)==1)continue;
				dp[k][i|(1<<k)] = min(dp[k][i|(1<<k)], dp[j][i]+d[j][k]);
			}
		}
	}
	int res =INF;
	for(int i =0;i <V;i++){
		res =min(res,dp[i][(1<<V)-1]+d[i][0]);
	}
	if(res==INF){
		cout <<-1<<endl;
	}else{
		cout <<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 5252
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pl;
#define all(a) (a).begin(),(a).end()
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,n) for(ll (i)=(n)-1;(i)>=0;i--)
#define SHOW(x) cout << #x << ": " << x << endl;
const ll INF=1e18;
const int iINF = 1e9;
int main(){
    int n,ans,cnt_2 = 0;
    bool flag = false;
    unordered_map<int,int>mp;
    cin>>n;
    ans = n;
    vector<int>a(n);
    rep(i,n){
        cin>>a[i];
        mp[a[i]]++;
    }
    for(auto itr:mp){
        if(itr.second%2 == 1){
            ans -= itr.second - 1;
        }
        else{
            ans -= itr.second - 2;
            cnt_2++;
        }
    }
    ans -= cnt_2 - cnt_2%2;
    if(cnt_2%2 == 1) ans -= 2;
    cout<<ans<<endl;
}


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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

const string YES = "Yes";
const string NO = "No";

void solve(std::string S){
    bool result = true;
    REP(i, S.size()) {
        if(i%2 == 0 && S[i] == 'L') result = false;
        if(i%2 == 1 && S[i] == 'R') result = false; 
    }

    cout << (result ? YES : NO ) << endl;
}

int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct ford_fulkerson{
    static const int INF=1001001001001001001;
    static const int MAX_V=2010;
    static const int SOURCE=MAX_V-2;
    static const int SINK=MAX_V-1;

    struct edge{
        int to,cap,rev;
        edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){}
    };
    vector<edge>G[MAX_V];
    bool used[MAX_V];

    void add_edge(int from,int to,int cap){
        G[from].push_back(edge(to,cap,G[to].size()));
        G[to].push_back(edge(from,0,G[from].size()-1));
    }

    int dfs(int v,int t,int f){
        if(v==t)return f;
        used[v]=true;
        for(int i=0;i<G[v].size();i++){
            edge &e=G[v][i];
            if(!used[e.to]&&e.cap>0){
                int d=dfs(e.to,t,min(f,e.cap));
                if(d>0){
                    e.cap-=d;
                    G[e.to][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return 0;
    }

    int max_flow(int s=SOURCE,int t=SINK){
        int flow=0;
        for(;;){
            memset(used,0,sizeof(used));
            int f=dfs(s,t,INF);
            if(f==0)return flow;
            flow+=f;
        }
    }
};

int N,M,L;
const int INF=1001001001001001001;
int dist[100][100];
void solve(){
    fill_n(*dist,100*100,INF);
    rep(i,N)dist[i][i]=0;

    rep(i,M){
        int a,b,c;
        cin>>a>>b>>c;
        chmin(dist[a][b],c);
        chmin(dist[b][a],c);
    }
    rep(k,N)rep(i,N)rep(j,N)chmin(dist[i][j],dist[i][k]+dist[k][j]);

    vpint qs;
    rep(i,L){
        int a,b;
        cin>>a>>b;
        qs.pb(pint(b,a));
    }

    sort(all(qs));

    ford_fulkerson ff;
    for(int i=0;i<L;i++){
        for(int j=i+1;j<L;j++){
            if(dist[qs[i].se][qs[j].se]<=qs[j].fi-qs[i].fi){
                ff.add_edge(i*2+1,j*2,1);
            }
        }
    }

    for(int i=0;i<L;i++){
        ff.add_edge(ford_fulkerson::SOURCE,i*2+1,1);
        ff.add_edge(i*2,ford_fulkerson::SINK,1);
    }

    cout<<L-ff.max_flow()<<endl;
}

signed main(){
    while(cin>>N>>M>>L,N||M||L)solve();
    return 0;
}

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

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

const int MAX_K = 160*80;
int dp[80][80][MAX_K+1];
int main() {
  int H, W; cin >> H >> W;

  int A[H][W], B[H][W];
  rep(i, H) rep(j, W)
    cin >> A[i][j];
  rep(i, H) rep(j, W)
    cin >> B[i][j];


  rep(i, H) rep(j, W) rep(k, MAX_K+1) {
    dp[i][j][k] = false;
  }
  dp[0][0][abs(A[0][0] - B[0][0])] = true;
  rep(i, H) rep(j, W) rep(k, MAX_K+1) {
    if (i+1 < H) {
      if (MAX_K >= k+abs(A[i+1][j] - B[i+1][j]))
        dp[i+1][j][k] |= dp[i][j][k+abs(A[i+1][j] - B[i+1][j])];
      dp[i+1][j][k] |= dp[i][j][abs(k-abs(A[i+1][j] - B[i+1][j]))];
    }
    if (j+1 < W) {
      if (MAX_K >= k+abs(A[i][j+1] - B[i][j+1]))
        dp[i][j+1][k] |= dp[i][j][k+abs(A[i][j+1] - B[i][j+1])];
      dp[i][j+1][k] |= dp[i][j][abs(k-abs(A[i][j+1] - B[i][j+1]))];
    }
  }
  rep(k, MAX_K+1) {
    if (dp[H-1][W-1][k]) {
      cout << k << endl;
      return 0;
    }
  }

  return 0;
}


Measured memory_bytes: 320256
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharp
{
    class Program
    {
        public static void Main()
        {
            var N = int.Parse(Console.ReadLine());
            int count = 0;

            for (var i = 1; i <= N; i++)
            {
                if(i.ToString().Length % 2 == 1)
                {
                    count++;
                }
            }

            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13140
#include<bits/stdc++.h>
#define ll long long
#define ajaychutiya ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

ll frog(ll arr[],ll i,ll n,ll dp[])
{
    //cout<<i<<'\n';
    //cout<<arr[i]<<'\n';
    
    if(i>=n-1)
    {
        dp[i]=0;
        return dp[i];
    }
    
    if(dp[i]!=-1)
    return dp[i];
    
    ll x,y;
    x=y=INT_MAX;
    
    if(i+1<=n-1)
    x=abs(arr[i+1]-arr[i])+frog(arr,i+1,n,dp);
    
    if(i+2<=n-1)
    y=abs(arr[i+2]-arr[i])+frog(arr,i+2,n,dp);
    
    dp[i]=min(x,y);
    return dp[i];
}

int main()
{
    ajaychutiya
    
     ll n;
     cin>>n;
     
     ll arr[n];
     ll dp[n];
     
     memset(dp,-1,sizeof(dp));

     for(ll i=0;i<n;i++)
     cin>>arr[i];
     
     ll ans=frog(arr,0,n,dp);
     cout<<ans;
}

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

int main () {
	
	int n=0;
	long long int x=0;
	map<long long int, int> mapa; 

	scanf("%d", &n);

	while (n--) {
		scanf("%lld", &x);
		x *= -1;
		if (mapa.find(x) == mapa.end()) mapa[x]=1;
		else mapa[x]++;
	}

	map<long long int, int>::iterator it;

	int c = 0;
	long long int a=0;

	for (it=mapa.begin(); it!=mapa.end(); it++) {

		if (it->second >= 2) {

			if (c == 0) {
				if (it->second >= 4) { a = (-it->first * -it->first); c++; }
				else a = -it->first;
				c++;
			}
			else if (c == 1) {
				a *= -it->first;
				c++;
			}
			else if (c>=2) break;
		}

	}

	if (c == 2) printf("%lld\n", a);
	else printf("0\n");

}

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

#ifdef MYDEBUG
#define dbp(x) cout<<#x<<": "<<x<<endl
#define dbp2(x,y) cout<<#x<<","<<#y<<": "<<x<<","<<y<<endl
#define dbp3(x,y,z) cout<<#x<<","<<#y<<","<<#z<<": "<<x<<","<<y<<","<<z<<endl
#else
#define dbp(x)
#define dbp2(x,y)
#define dbp3(x,y,z)
#endif
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define all(x) x.begin(), x.end()
#define rep(i, from, to) for(int i=from; i<to; ++i)

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  size_t last = v.size() - 1;
  for (size_t i = 0; i < v.size(); ++i) {
    out << v[i];
    if (i != last)
      out << ",";
  }
  out << "]";
  return out;
}

int h, w;
const int maxh = 110;
char a[maxh][maxh];
void solve() {
  cin >> h >> w;
  fill(a[0], a[0] + w + 2, '#');
  fill(a[h + 1], a[h + 1] + w + 2, '#');
  for (int i = 1; i <= h; ++i) {
    a[i][0] = a[i][w + 1] = '#';
    for (int j = 1; j <= w; ++j) {
      cin >> a[i][j];
    }
  }
  for (int i = 0; i <= h + 1; ++i) {
    for (int j = 0; j <= w + 1; ++j) {
      cout << a[i][j];
    }
    cout << endl;
  }
}

int main() {
  solve();
  return 0;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Pine1999
 */

#include <bits/stdc++.h>

using namespace std;

class EPickingGoods {
public:
    void solve(istream& in, ostream& out) {
        int r, c, kk;
        in >> r >> c >> kk;
        vector<vector<int>> cost(r, vector<int> (c));
        for (int i = 0; i < kk; ++i) {
            int rr, cc, v;
            in >> rr >> cc >> v;
            --rr; --cc;
            cost[rr][cc] = v;
        }
        vector<vector<vector<long long>>> dp(r, vector<vector<long long>> (c, vector<long long> (4)));
        dp[0][0][1] = cost[0][0];
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                if (i > 0) {
                    for (int k = 0; k < 4; ++k) {
                        dp[i][j][0] = max(dp[i - 1][j][k], dp[i][j][0]);
                        dp[i][j][1] = max(dp[i - 1][j][k] + cost[i][j], dp[i][j][1]);
                    }
                }
                if (j > 0) {
                    for (int k = 0; k < 3; ++k) {
                        dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j - 1][k] + cost[i][j]);
                    }
                    for (int k = 0; k < 4; ++k) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k]);
                    }
                }
            }
        }
        long long ans = 0;
        for (int i = 0; i < 4; ++i) {
            ans = max(ans, dp[r - 1][c - 1][i]);
        }
        out << ans << '\n';
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    EPickingGoods solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

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

using namespace std;

const int maxn = 10000010;
const int maxa = 5010;
const int mod = 1e9+7;

int n, a;

int fac[maxn+maxa], ifac[maxn+maxa], inv[maxn+maxa];

int binom(int x, int y) {
	if (y > x) return 0;
	return 1LL * fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}

int cal(int x, int y) {
	if (!y) return 1;
	if (x) return 1LL * fac[x + y - 1] * ifac[x - 1] % mod;
	else return 0;
}

int main() {
	scanf("%d%d", &n, &a);
	fac[0] = ifac[0] = 1, inv[1] = 1;
	for (int i = 2; i <= n+a; i++) inv[i] = mod - 1LL * inv[mod % i] * (mod / i) % mod;
	for (int i = 1; i <= n+a; i++) {
		fac[i] = 1LL * fac[i-1] * i % mod;
		ifac[i] = 1LL * ifac[i-1] * inv[i] % mod;
	}
	int ans = 0;
	for (int p = 1; p <= a; p++) {
		for (int k = 0; k < p; k++) {
			if (k == p-1) {
				int K = binom(p-1, k); if (k & 1) K = mod - K;
				for (int s = p-1; s <= a-1; s++) {
					int w = 1;
					w = 1LL * w * binom(a-p, s-p+1) % mod;
					w = 1LL * w * cal(s-k, n-a) % mod;
					w = 1LL * w * fac[a-s-1] % mod;
					w = 1LL * w * cal(p-1-k, s-p+1) % mod;
					w = 1LL * w * fac[p-1-k] % mod;
					ans = (ans + 1LL * K * w % mod) % mod;
				}
			} else {
				int K = binom(p-1, k); if (k & 1) K = mod - K;
				int w = 1;
				w = 1LL * w * (p-1-k) % mod;
				w = 1LL * w * fac[a-p] % mod;
				w = 1LL * w * fac[p-k+n-a-2] % mod;
				w = 1LL * w * binom(n-k-1, a-p) % mod;
				ans = (ans + 1LL * K * w % mod) % mod;
			}
		}
	}
	// 一个自环都没得
	{
		for (int k = 0; k <= a; k++) {
			int K = binom(a, k); if (k & 1) K = mod - K;
			ans = (ans + 1LL * fac[a - k] * cal(a - k, n - a) % mod * K % mod) % mod;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 121012
using System;

namespace A___Cats_and_Dogs
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var a = int.Parse(input[0]);
            var b = int.Parse(input[1]);
            var x = int.Parse(input[2]);
            if (a + b >= x && x >= a)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <list>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;
 
struct node {
    int id, parent, left, right;
};
 
int reconstruct(queue<node> &nodes, queue<int> &pre, queue<int> &in, int parent){
    if(!in.size()) return -1;
     
    node n;
    n.parent = parent;
    n.id = pre.front();
    pre.pop();
     
    bool toA = true;
    queue<int> inA, inB;
    while(in.size()){
        if(in.front() == n.id){
            in.pop();
            toA = false;
            continue;
        }
        (toA ? inA : inB).push(in.front());
        in.pop();
    }
     
    n.left = reconstruct(nodes, pre, inA, n.id);
    n.right = reconstruct(nodes, pre, inB, n.id);
     
    nodes.push(n);
    return n.id;
}
 
int main() {
    int n;
    scanf("%d", &n);
     
    queue<int> pre;
    for(int i = 0; i < n; i++){
        int num;
        scanf("%d", &num);
        pre.push(num);
    }
     
    queue<int> in;
    for(int i = 0; i < n; i++){
        int num;
        scanf("%d", &num);
        in.push(num);
    }
     
    queue<node> nodes;
    reconstruct(nodes, pre, in, -1);
     
    while(nodes.size()){
        printf("%d%c", nodes.front().id, nodes.size() == 1 ? '\n' : ' ');
        nodes.pop();
    }
     
    return 0;
}


Measured memory_bytes: 3240
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <string>

using namespace std;

int cnta = 0;
int cntb = 0;
int cntc = 0;

int main() {

	string s;
	cin >> s;

	for (int i = 0; i < 3; ++i) {
		if (s[i] == 'a') {
			cnta++;
		}
		if (s[i] == 'b') {
			cntb++;
		}
		if (s[i] == 'c') {
			cntc++;
		}
	}

	if (cnta == 1 && cntb == 1 && cntc == 1) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <cstdlib>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include <assert.h>
#include<map>
#include<set>
#include<bitset>
#include <iomanip>
#include<stack>
#include <unordered_map>
#include<cmath>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
// #define pi acos(-1)
// #include<bits/stdc++.h>
#define INF 0x7f7f7f7f //2139062143
#define INF1 0x3f3f3f3f //1061109567
#define INF2 2147483647
#define llINF 9223372036854775807
#define pi 3.14159265358979323846264338327950254
#define pb push_back
#define ll long long
#define debug cout << "debug\n";
#define STDIN freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);//************************************
#define Quick ios::sync_with_stdio(false);cin.tie(NULL);
#define scai(x) scanf("%d", &x)
#define sca2i(x, y) scanf("%d %d", &x, &y)
#define scaf(x) scanf("%lf", &x)
#define sca2f(x, y) scanf("%lf %lf", &x, &y)
#define For(m,n) for (int i = m;  i < n; i++)
#define PII pair<int,int>
#define PLL pair<long, long>
#define ft first
#define sd second
#define pb push_back


const int maxn=333333,mod=1000000009;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){    char ch=getchar();int x=0,f=0;    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();    return f?-x:x;    } 

ll A, B, N;

ll f(ll x)
{
    // return (ll)(A*x*1.0/B) - A*(ll)(x*1.0/B);
    return floor(A*x/B) - A*floor((x/B));
}
// ll ef(ll l,ll r)//三分
// {
//     double eps = 0.01;
//     while(r - l > eps) //保证精度，最好是k+2位精度哦！
//     {
//         ll lmid=l+(r-l)/3,rmid=r-(r-l)/3;
//         if(f(lmid)<=f(rmid)) l=lmid;
//         else r=rmid;
//     }
//     return r;
// }
int main()
{
    // STDIN;
    cin >> A >> B >> N;
    // ll l = 1, r = B - 1;
    // while (r - l > 0)
    // {
        
    //     ll mid = l + r >> 1;//cout << mid << endl;
    //     cout << mid << " " <<f(mid) << endl;
    //     if (f(mid) > N)
    //     {
    //         r = mid;
    //     }
    //     else l = mid + 1;
    // }
    // cout << l << endl;

    // int lll = max(1, B-1);
    // if (N >= B) cout << f(B-1) << endl;
    // else
    //     cout << f(N) << endl;

    cout << f(min(B-1, N)) << endl;
    // for (int x = 1; x <= 1000; x ++)
    // {
    //     cout << f(x) << endl;
    // }
}

Measured memory_bytes: 3160
using System;

class Program
{
    static void Main()
    {
        string[] input = Console.ReadLine().Split(' ');
        int h = int.Parse(input[0]);
        int w = int.Parse(input[1]);
        string[] input2 = Console.ReadLine().Split(' ');
        int h2 = int.Parse(input2[0]);
        int w2 = int.Parse(input2[1]);
        int ans = h * w - h2 * w - w2 * h + h2 * w2;
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 11092
from itertools import accumulate

def unite_intervals(lst: list) -> list:

    # 終点の最大値の分だけ配列を確保(0-indexed)
    n = len(lst)
    mx = max([lst[i][1] for i in range(n)])
    imos = [0] * (2*(mx+1) + 2)
    
    # 始点を+1, 終点を-1する
    for st, ed in lst:
        imos[2*st + 1] += 1
        imos[2*ed] -= 1
        
    imos_cum = list(accumulate(imos))

    # 総合的な[start, last)区間を答えに詰めていく
    ans = []
    start = -1
    last = -1
    for i in range(mx+2):
        if imos_cum[2*i] == 0 and imos_cum[2*i+1] > 0:
            start = i
            
        elif imos_cum[2*i+1] > 0 and imos_cum[2*i+2] == 0:
            last = i+1
            
            ans.append((start, last))
            start = -1
            last = -1
        
    return ans

import sys
sdin = sys.stdin.readline

n,c = map(int, sdin().split())

dic = {}  
for i in range(c):
    dic.update({i+1: []})
    
# 各チャンネルの録画時刻を記録
ch_st = []
max_t = 0
for _ in range(n):
    s,t,ch = map(int, sdin().split())
    max_t = max(max_t, t)
    dic[ch].append((max(0,s-1),t))
    
# 被っている部分をマージする
for ch in range(c):
    ch += 1
    if len(dic[ch]) > 0:
        dic[ch] = unite_intervals(dic[ch])
    
# imos法で
imos = [0]*(max_t+1)
for ch in range(1,c+1):
    for s, t in dic[ch]:
        imos[s] += 1
        imos[t] -= 1
        
imos = list(accumulate(imos))
print(max(imos))

Measured memory_bytes: 22556
#include "bits/stdc++.h"
using namespace std;

int selectionSort(vector<int>& A, int N);

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

	vector<int> A(N);
	for (int i = 0; i < N; i++) cin >> A.at(i);
	
	int count = selectionSort(A, N);

	for (int i = 0; i < N; i++) {
		if (i) cout << " ";
		cout << A.at(i);
	}
	cout << endl;
	cout << count << endl;
	
	return 0;
}


int selectionSort(vector<int>& A, int N) {

	int count = 0;
	for (int i = 0; i < N; i++)
	{
		int minJ = i;
		for (int j = i; j < N; j++)
		{
			if (A.at(j) < A.at(minJ)) {
				minJ = j;
			}
		}
		
		if (minJ != i) {
			swap(A.at(minJ), A.at(i));
			count++;
		}
	}
	return count;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, m,n) for (int i = m; i < (int)(n); i++)
int main(){
  string S;
  cin>>S;
  if(S=="ABC"){cout<<"ARC"<<endl;}
  else{cout<<"ABC"<<endl;}
}

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

g = [[] for _ in range(N)]
for a, b in AB:
	a, b = a - 1, b - 1
	g[a] += [b]
	g[b] += [a]

def dfs(v, visited):
	#print(visited)
	if v in visited:
		return False
	if N - 1 == len(visited):
		return True
	count = 0
	for n in g[v]:
		count += dfs(n, visited | {v})
	return count

print(dfs(0, set()))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1e9+7
#define PI acos(-1.0)
#define ll long long int // 64bit, 9*10^18
#define INF 1000000001

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
//---------------------------
ll gcd(ll a, ll b)
{
  for (;;)
  {
    if (a == 0) return b;
    b %= a;
    if (b == 0) return a;
    a %= b;
  }
}
ll lcm(ll a, ll b)
{
    ll temp = gcd(a, b);

    return temp ? (a / temp * b) : 0;
}

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int n;cin>>n;
  ll t[100];
  ll ans=1;
  REP(i,n){
    cin>>t[i];
  }
  REP(i,n){
    ans=lcm(ans, t[i]);
  }
  P(ans);
  return 0;
}


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

using LL = long long;

int main () {
	LL n, s;
	std::cin >> n >> s;
	if (s == n) {
		std::cout << n+1 << "\n";
	} else {
		LL ans = 1e18;
		for (LL b = 2; b * b <= n; ++b) {
			LL sum = 0, tmp = n;
			while (tmp > 0) {
				sum += tmp % b;
				tmp /= b;
			}
			if (sum == s)
				ans = std::min (ans, b);
		}
		std::cerr << "ans = " << ans << "\n";
		for (LL p = 1; p * p <= n; ++p) {
			LL q = s - p, b = (n - q) / p;
			if (p * b + q == n and p < b and q < b and p > 0 and q >= 0)
				ans = std::min (ans, b);
		}
		if (ans == 1e18)
			ans = -1;
		std::cout << ans << "\n";
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
const ll mod=1000000007;
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)

int main() {
  int n;cin>>n;
  vector<int> v(n);
  int x=0;
  for(int i=0;i<n;++i){
    int t;cin >> t;
    x+=t;
    v[i] = t;
  }
  int p1=x/n,p2=x/n+1;
  int out1= 0,out2= 0;
  for(int i=0;i<n;++i){
    out1+=(v[i]-p1)*(v[i]-p1);
    out2+=(v[i]-p2)*(v[i]-p2);
  }
  cout << min(out1,out2) << endl;
  return 0;
}


Measured memory_bytes: 256
//Radhe Radhe
#include<bits/stdc++.h>
#define godspeed  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define en '\n'
#define rep(i,n)    for(ll i=0; i<n; i++)
#define rep1(i,a,b)    for(ll i=a; i<=b; i++)
#define repVect(i,n)    for(ll i=0; i<sum.size(); i++)
#define fixed cout.setf(ios::fixed);
#define Precise cout.precision(7);
#define yes cout<<"Yes"<<'\n'
#define no cout<<"No"<<'\n'
using namespace std;

int main()
{
    godspeed
    ll  n,i,j,k;
    string s;
    ll ans=0;
    cin>>n;
    for(i=1; i<n; i++)
    {
     ll lol=n/i;
     if(n%i) ans+=lol;
     else ans+=lol-1;
        /*for(j=1; j<n; j++)
        {
            if(i*j<n){

                ans++;
            cout<<++noo<<": "<<i<<" "<<j<<" "<<i*j<<en;
            }
        }*/
    }
    cout<<ans<<en;
    return 0;
}






Measured memory_bytes: 3584
import java.util.Scanner;

/**
 * Created by hwzheng on 2016/12/13.
 */
public class Main {
    public static void main(String[] a) {
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        int j = scanner.nextInt();
        int k = i * j;
        int l = (i + j) * 2;
        System.out.println(k + " " + l);
    }
}

Measured memory_bytes: 26072
#include<iostream>
#include<algorithm>
#define F(n) for(int i=0;i<n;i++)
using namespace std;
long a[100000],ans=10000000000;
int main() {
	int n, k;
	cin >> n >> k;
	F(n)cin >> a[i];
	for (int i = 0; i < n - k+1; i++) {
		long r = a[i]; long l = a[i + k-1];
		ans=min(abs(r) + abs(l-r),ans);
		ans=min(abs(l) + abs(r-l),ans);
	}
	cout << ans << endl;
}

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

using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define all(v) v.begin(),v.end()
#define ve vector
#define vi vector<int>
#define vi2 vector<vi>
#define vl vector<long long>
#define vl2 vector<vl>

template <class T> T maxAny(T a, T b){
    if(a > b) return a;
    else return b;
}

template <class T> T minAny(T a, T b){
    if(a > b) return b;
    else return a;
}

int main(){
    long long n, rnum = 0;
    string c;
    cin >> n >> c;
    rep(i, c.size()){
        if(c[i] == 'R') rnum++;
    }
    long long index = rnum;
    rep(i, index){
        if(c[i] == 'R') rnum--;
    }
    cout << rnum << endl;
}

Measured memory_bytes: 3752
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
S = [int(s) for s in input()] + [1]

r = -1
ans = 0
cnt = 0
used = [0]*(N + 1)
for l in range(N):
    if S[l] + S[l-1] == 0:
        continue
    while r < N and used[r] - used[l-1] <= K:
        r += 1
        if S[r-1] == 1 and S[r] == 0:
            used[r] = used[r - 1] + 1
        else:
            used[r] = used[r - 1]
    ans = max(ans, r-l)

print(ans)


Measured memory_bytes: 8260
N = int(input())


A = [0]*N
for i in range(N):
    A[i] = int(input())

dammyA = sorted(A)
maxfir = dammyA[-1]
maxsec = dammyA[-2]


for i in range(N):
    if A[i]==maxfir:
        print(maxsec)
    else:
        print(maxfir)

Measured memory_bytes: 58328
#include <bits/stdc++.h>
 
using namespace std;
 
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
ll n,q,k;

ll a[105];
int main() {
slld(n);
for(int i=1;i<=n;i++)
{
	slld(a[i]);
}

ll ans=a[1];
for(int i=2;i<=n;i++)
	ans=((ans/(__gcd(a[i],ans)))*(a[i]/__gcd(ans,a[i])))*__gcd(ans,a[i]);
plld(ans);
	return 0;
           } 

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

int N,K;
vector<int> H;

int main() {
    cin>>N>>K;
    H.resize(N);
    for (int i=0; i<N; i++) cin>>H[i];
    sort(H.begin(),H.end());
    long ans=0;
    for (int i=0; i<N-K; i++) {
        ans+=H[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<iomanip>
using namespace std;

int main(){
    long long int n,z=0;
    double ans=0;
    cin>>n;
    vector<double>a(1000000);
    vector<double>b(1000000);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end(),greater<>());
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1;j++){
            if(ans<(a[i]+a[i+1])/(a[j]-a[j+1])&&i!=j&&i+1!=j&&i!=j+1){
                ans=(a[i]+a[i+1])/(a[j]-a[j+1]);
            }
        }
    }
    cout<<fixed <<setprecision(6)<<ans<<endl;
   return 0;
}



Measured memory_bytes: 18400
N, P = map(int, input().split())
def fact(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append((i, cnt))

    if temp!=1:
        arr.append((temp, 1))

    if arr==[]:
        arr.append((n, 1))

    return arr
ans =1
for yakusu, kosu in fact(P):
  while kosu >= N:
    ans *= yakusu
    kosu -= N
print(ans)

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

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

const int maxn = 5e5 + 5;

int a[maxn], b[maxn], d[maxn], N, D, Q;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> D;
  a[0] = D;
  for(int i = 1; i <= N; ++i){
    cin >> d[i];
    a[i] = min(a[i - 1], abs(a[i - 1] - d[i]));
  }
  b[N] = 1;
  for(int i = N - 1; i >= 1; --i){
    if(b[i + 1] <= d[i + 1] / 2) b[i] = b[i + 1];
    else b[i] = b[i + 1] + d[i + 1];
  }
  cin >> Q;
  while(Q--){
    int p; cin >> p;
    cout << (a[p - 1] >= b[p] ? "YES\n" : "NO\n");
  }
}


Measured memory_bytes: 7808
INF = 2**50
def solve(n, m, a):
    c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dp = [-INF] * (n+10)
    dp[0] = 0
    for d in range(n+1):
        for i in range(m):
            nd = d + c[a[i]]
            dp[nd] = max(dp[nd], 10*dp[d] + a[i])
    return dp[n]

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

Measured memory_bytes: 14692
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <list>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip> // setprecisionを使用するのに必要 cout << fixed << setprecision(15) << p でpを小数点以下15桁表示
using namespace std;
#define REPD(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) REPD(i, 0, n)
typedef long long ll;
#define fin(ans) cout << (ans) << '\n'
/*

*/
int main()
{
    string S;
    bool ans = true;
    int count=1;
    cin >> S;
    sort(S.begin(),S.end());
    if(S.length() == 1){fin("No");return 0;}
    REPD(i,1,S.length()){
        if(S[i] == S[i-1]) count++;
        else{
            if(count%2){
                ans = false;break;
            }else{
                count = 1;
            }
        }
    }
    if(ans)fin("Yes");
    else fin("No");
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

const int N = 1000000;
bool isprime[N];

int main() {
    FOR(i,2,N-1) isprime[i] = 1;
    FOR(i,2,N-1){
        if (!isprime[i]) continue;
        int x = 2*i;
        while (x < N){
            isprime[x] = 0;
            x += i;
        }
    }
    int a, d, n;
    while (cin >> a >> d >> n && n){
        while (n){
            if (isprime[a]) n--;
            a += d;
        }
        cout << a - d << endl;
    }
    return 0;
}

Measured memory_bytes: 4056
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<iomanip>
#include<stack>
#include<queue>
using namespace std;

typedef long long ll;

ll mod_pow(ll x, ll n, ll mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

int main(){
	ll m, n;
	cin >> m >> n;
	cout << mod_pow(m, n, 1000000007) << endl;
	return 0;
}


Measured memory_bytes: 3092
from collections import deque

X = input()
stack = deque([X[0]])
for i in range(1, len(X)):
    if X[i] == 'S':
        stack.appendleft(X[i])

    if X[i] == 'T':
        if stack:
            check = stack.popleft()
            if check == 'T':
                stack.appendleft(check)
                stack.appendleft(X[i])
        else:
            stack.appendleft(X[i])

print(len(stack))


Measured memory_bytes: 10684
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define poly vector<ll>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x=0;char ch=gc();bool positive=1;
	for(;!isdigit(ch);ch=gc()) if(ch=='-') positive=0;
	for(;isdigit(ch);ch=gc()) x=x*10+ch-'0';
	return positive?x:-x;
}
inline void write(ll x){
	if(x<0){
		x=-x;putchar('-');
	}
	if(x>=10) write(x/10);
	putchar('0'+x%10);
}
inline void writeln(ll x){write(x);puts("");}
inline void writep(ll x){write(x);putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=5e5+5,mo=998244353;
int fac[N],inv[N];
int ksm(int x,int p){
	int res=1;
	for(;p;p>>=1,x=(ll)x*x%mo){
		if(p&1) res=(ll)res*x%mo;
	}
	return res;
}
void init(int n){
	For(i,fac[0]=1,n) fac[i]=(ll)i*fac[i-1]%mo;
	inv[n]=ksm(fac[n],mo-2);
	Rep(i,n-1,0) inv[i]=(ll)inv[i+1]*(i+1)%mo;
}
int C(int n,int m){
	return (ll)fac[n]*inv[m]%mo*inv[n-m]%mo;
}
int main(){
	init(N-1);
	int n=read(),m=read(),ans=0;
	For(i,0,min(n,m)){
		int ssw=(ll)C(n,i)*C(m,i)%mo*fac[i]%mo;
		int ksg=(ll)ksm(n+1,m-i)*ksm(m+1,n-i)%mo;
		ssw=(ll)ssw*ksg%mo;
		if(i%2) ans=(ans+mo-ssw)%mo;
		else ans=(ans+ssw)%mo;
	}
	cout<<ans;
}

Measured memory_bytes: 4096
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from fractions import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    def yakusuu(N):
        n = int(N**.5)+1
        res1 = []
        res2 = []
        for i in range(1, n):
            if N%i==0:
                res1.append(i)
                if N!=i**2:
                    res2.append(N//i)
        res2.reverse()
        return res1+res2
        # 約数のリストを返す

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    
    kouho = yakusuu(sum(a))

    for i in kouho[::-1]:
        nega = [0]*n
        posi = [0]*n
        for j in range(n):
            posi[j] = a[j] % i
        posi.sort()
        for j in range(n):
            nega[j] = posi[j] - i
        posi = [0] + posi
        nega = [0] + nega
        posi = list(accumulate(posi))
        nega = list(accumulate(nega))
        total = 10**10
        for j in range(1, n+1):
            total = min(total, max(posi[j], -(nega[-1]-nega[j])))
        if total <= k:
            print(i)
            break
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 69224
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define fi first
#define se second
static const int INF = 1e9;
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
string board[1001];//??\?????¨??????
int d[1001][1001];//???????????¢?´¢???????????¨???????????§??????????????¢?????\????????????
int h, w, n;
pair<int, int> point[10];//fi=y??§?¨? se=x??§?¨?
int ans = 0;
bool flag;
//???????????¢?´¢
void bfs(void){
	rep(i, n){//??????????????¨??´?????????
		int starty = point[i].fi, startx = point[i].se;//start
		int endy = point[i + 1].fi, endx = point[i + 1].se;//end
		queue<pair<int, int> > q;
		q.push(make_pair(starty, startx));//start???????????\??????
		rep(i, h) rep(j, w) d[i][j] = INF;//?????????
		d[starty][startx] = 0;
		flag = false;
		while(!q.empty()){
			pair<int, int> now;
			now = q.front(); q.pop();
			rep(j, 4){//4??????????????????
				int y = now.fi + dy[j];
				int x = now.se + dx[j];
				if(y < 0 || h <= y || x < 0 || w <= x) continue;//?????????
				if(d[y][x] == INF && board[y][x] != 'X'){
					d[y][x] = d[now.fi][now.se] + 1;//???????????¢????¨????
					q.push(make_pair(y, x));
				}
				if(y == endy && x == endx){
					flag = true;
					ans += d[y][x];//?????¢????¶?????????????
					break;
				}
			}
			if(flag == true) break;
		}
	}
	return;
}

int main(void){
	cin >> h >> w >> n;
	rep(i, h){
		cin >> board[i];
	}

	//start????????¨??????????????´?????????????±?????????????
	rep(i, h) rep(j, w){
		if(board[i][j] == 'S'){
			point[0].fi = i; point[0].se = j;
		}else if ('1' <= board[i][j] && board[i][j] <= '9'){
			int tmp = board[i][j] - '0';
			point[tmp].fi = i; point[tmp].se = j;
		}
	}
	bfs();
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7844
#include <stdio.h>
int main(void){
  int N;
  if(scanf("%d",&N)<1) return 1;
  
  char S[N],T[N];
  if(scanf("%s%s",&S,&T)<2) return 1;
  
  for(int i=0;i<N;i++){
    printf("%c%c",S[i],T[i]);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 128
x1, y1, x2, y2 = map(int, input().split())
q = int(input())

p1p2 = complex(x2 - x1, y2 - y1)
d2_p1p2 = abs(p1p2) ** 2
conj_p1p2 = p1p2.conjugate()

while q:
    q -= 1
    x0, y0 = map(int, input().split())
    p1p0 = complex(x0 - x1, y0 - y1)
    t = (conj_p1p2 * p1p0).real / d2_p1p2
    print(x1 + p1p2.real * t, y1 + p1p2.imag * t)

Measured memory_bytes: 7692
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <climits>
#include <cassert>
#include <algorithm>
#include <utility>

using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;
using VVI = vector<vector<long long int> >;

int main(void) {
    Int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    cout << (h2 - h1) * 60 + (m2 - m1) - k << endl;
    return 0;
}


Measured memory_bytes: 3620
#include<iostream>

void returnNo()
{
	std::cout << "No\n";
}
	
int main()
{
	int a, b, c;
	std::cin >> a >> b >> c;
	if(a<b){
		if(b<c){
			std::cout << "Yes\n";
		} else {
			returnNo();
		}
	} else {
		returnNo();
	}
	return 0;
}

Measured memory_bytes: 1124
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
#define foreach(c,it) for (__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
using namespace std;
int n,m,q,i,j,v[1<<18],w[1<<18];
vector<pair<int,int> > res[1<<12],tmp;
bool cmp(pair<int,int> x,pair<int,int> y){
	if(x.first==y.first) return x.second>y.second;
	return x.first<y.first;
}
int main(){
	cin>>n;
	m=2;
	while(m*2<n&&m*m/4<n) m=m*2;
	rep(i,n){
		cin>>v[i]>>w[i];
	}
	res[1].push_back(make_pair(0,0));
	res[1].push_back(make_pair(w[1],v[1]));
	rep(i,m-1){
		sort(res[i].begin(),res[i].end(),cmp);
		tmp.clear();
		for(j=0;j<res[i].size();j++){
			if(tmp.empty()||res[i][j].second>tmp.back().second){
				tmp.push_back(res[i][j]);
			}
		}
		res[i]=tmp;
/*		cerr<<i<<":  ";
		for(j=0;j<res[i].size();j++){
			cerr<<res[i][j].first<<' '<<res[i][j].second<<"     ";
		}cerr<<endl;*/
		if(i*2>=m) continue;
		for(j=0;j<res[i].size();j++){
			res[i*2].push_back(res[i][j]);
			if(res[i][j].first+w[i*2]<=100000) res[i*2].push_back(make_pair(res[i][j].first+w[i*2],res[i][j].second+v[i*2]));
			res[i*2+1].push_back(res[i][j]);
			if(res[i][j].first+w[i*2+1]<=100000) res[i*2+1].push_back(make_pair(res[i][j].first+w[i*2+1],res[i][j].second+v[i*2+1]));
		}
	}
	cin>>q;
	while(q--){
		int x,y,ans=0;
		cin>>x>>y;
		vector<pair<int,int> > seq;
		while(x>=m){
			seq.push_back(make_pair(w[x],v[x]));
			x/=2;
		}
		for(i=0;i<(1<<seq.size());i++){
			int sw=0,sv=0;
			for(j=0;j<seq.size();j++){
				if((i>>j)&1){
					sw+=seq[j].first;
					sv+=seq[j].second;
				}
			}
			if(sw>y) continue;
			vector<pair<int,int> >::iterator it=upper_bound(res[x].begin(),res[x].end(),make_pair(y-sw,1<<30));
			it--;sv+=it->second;
			ans=max(ans,sv);
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 11100
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }



int N;
void solve(string str, int cur = 0) {
    if (str.size() == N) {
        cout << str << endl;
        return;
    }
    for (int i = 0; i < cur; ++i) {
        char c = 'a' + i;
        solve(str + c, cur);
    }
    char c = 'a' + cur;
    solve(str + c, cur + 1);
}

int main() {
    while (cin >> N) {
        string res = "";
        solve(res);
    }
}

















Measured memory_bytes: 1536
//#define _USE_MATH_DEFINES
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#pragma GCC diagnostic ignored "-Wmissing-declarations"
#define FINAL_OUT(x) {cout << (x) << '\n'; exit(0); }
inline int safe_mul(const int x, const int y) __attribute__ ((warn_unused_result));


int main()
{
//    freopen("in.txt","r", stdin);
//    freopen("floor4.out", "w", stdout);
//    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    int a,b;
    cin >> a>> b;
    if (a%2 != b % 2)
        cout << "IMPOSSIBLE" << endl;
    else
        cout << (a + b)/2 << endl;
}


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

#define FREP(i,a,b) for(int i=a;i<b;i++)
#define REP(i,n) FREP(i,0,n)
#define PB push_back
#define mod 1000000007
#define endl "\n"
#define ll long long
#define MP make_pair
#define vi vector<ll>
#define si set<ll>
#define mi map<ll, ll>
#define pri(a,n) REP(i,n)cout<<a[i]<<" ";
#define sa(a,n) sort(a,a+n)
#define sra(a,n) sort(a, a + n, greater<ll>())
#define sv(v) sort(v.begin(),v.end())
#define srv(v) sort(v.rbegin(),v.rend())
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

ll bin(ll a, ll b)
{
	if (b == 0)
		return 1;
	if (b % 2 == 0)
		return bin((a * a) % mod , b / 2) % mod;
	return ((a % mod) * (bin((a * a) % mod , b / 2) % mod)) % mod;
}

void g_o_a_l()
{
	ll n, q;
	ll a, b;
	cin >> a >> b;
	if (b % 2)
	{
		cout << "No";
	}
	else
	{
		if (b <= 4 * a && b >= 2 * a)
			cout << "Yes";
		else
			cout << "No";
	}

}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	FASTIO;

	ll t = 1;
	// cin >> t;
	while (t--)
	{
		g_o_a_l();
	}

}

Measured memory_bytes: 3652
expressions = input( ).split( " " )
stack = []
for op in expressions:
	if "+" == op:
		b = stack.pop( )
		a = stack.pop( )
		stack.append( a + b )
	elif "-" == op:
		b = stack.pop( )
		a = stack.pop( )
		stack.append( a - b	)
	elif "*" == op:
		b = stack.pop( )
		a = stack.pop( )
		stack.append( a * b )
	else:
		stack.append( int( op ) )
print( stack.pop( ) )

Measured memory_bytes: 6724
#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 <iomanip>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int MAX = 2e5 + 5;
const int MOD = 1e9 + 7;
vector<int> adj[MAX];
int n;

inline int add(int a, int b) { return (a + b) % MOD; }
inline int sub(int a, int b) { return (a - b + MOD) % MOD; }
inline int mult(int a, int b) { return (1LL * a * b) % MOD; }

int f_exp(int x, int e) {
    if (e == 0) return 1;
    if (e & 1) return mult(x, f_exp(x, e - 1));
    return f_exp(mult(x, x), e / 2);
}

inline int inv(int x) {
    return f_exp(x, MOD - 2);
}

ii dfs(int node, int father) {
    int mv = 0;
    int ev = 0;
    int c = 0;
    int size = 1; 

    for (auto &each : adj[node]) {
        if (each == father) continue;
        int v, c_size;
        tie(v, c_size) = dfs(each, node);
        
        mv = add(mv, f_exp(2, c_size));
        ev = add(ev, v);
        size += c_size;
        c++;
    }

    if (father != -1) {
        mv = add(mv, f_exp(2, n - size));
        c++;
    }

    mv = sub(mv, (c - 1 + MOD) % MOD);
    mv = add(mv, f_exp(2, n - 1));
    ev = add(ev, mv);

    return make_pair(ev, size);
}

void solve() {
    cin >> n;
    fori (i, 0, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int k = dfs(1, -1).first;
    int x = (-mult(inv(f_exp(2, n)), k) + MOD) % MOD;
    int ans = add(x, n);
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}



Measured memory_bytes: 25588