akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    ll n,m; cin>>n>>m;
    string s; cin>>s;
    vector<ll> res;
    ll loc=n;
    while(loc>0){
        bool ifpossible=false;
        for(ll i=m; i>0; i--){
            if(loc-i>=0 && s[loc-i]=='0'){
                res.push_back(i);
                loc-=i;
                ifpossible=true;
                break;
            }
        }
        if(!ifpossible){
            cout<<-1<<endl;
            return 0;
        }
    }
    ll kaisu=res.size();
    for(ll i=kaisu-1; i>=0; i--){
        cout<<res[i]<<' ';
    }
    cout<<endl;
    return 0;
}

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

const int N = 2e5 + 100;
vector<int> G[N];
int U[N] , V[N];
int mn[N] , mx[N];
long long ans;
long long n;
long long tot = 0;
void dfs(int s, int p){
  mn[s] = s;
  mx[s] = s;
  for(auto it : G[s]){
    if(it == p) continue;
    dfs(it , s);
    int a = s , b = it;
    if(a < it)
      ans += a*(b-max(a , mn[it]));
    else 
      ans += (min(mx[it] , a)-b)*(n-a+1);
    mn[s] = min(mn[s] , mn[it]);
    mx[s] = max(mx[s] , mx[it]);
  }
}
int main(){
  ios_base::sync_with_stdio(false);
  cout.tie(0); cin.tie(0);
  long long ans = 0;
   cin >> n;
  long long u , v;
  //ans = ((n)*(n+1))/2;
  for(long long i = 1 ;i <= n ; ++i)
    tot += (i*(n-i+1));
  for(int i = 1;i <= n-1 ; ++i){
    cin >> u >> v; 
    G[u].push_back(v);
    G[v].push_back(u);
    if(u > v) swap(u , v);
    ans += (u*(n-v+1));
    //ans += u*(v-u);
    //ans += (v-u)*(n-v+1);
  }
  //dfs(1 , -1);
  cout << tot-ans << endl;
  return 0;
}


Measured memory_bytes: 14984
#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;
using namespace std;

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

int main(){
	int n, m;
	cin >> n >> m;

	vector<vector<long long>> a(n, vector<long long>(3));
	rep(i,n){
		rep(j,3) cin >> a[i][j];
	}


	long long ans = 0;
	rep(s,1 << 3){
		vector<long long> p(n);

		rep(i,n){
			long long cnt = 0;
			rep(j,3){
				if(s >> j & 1){
					cnt += a[i][j];
				}else{
					cnt -= a[i][j];
				}
			}
			p[i] = cnt;
		}

		sort(all(p), greater<long long>());

		long long sum = 0;
		rep(i,m){
			sum += p[i];
		}
		ans = max(ans, sum);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
using Yorukatsu057.Questions;
using Yorukatsu057.Extensions;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Yorukatsu057.Questions
{
    /// <summary>
    /// https://atcoder.jp/contests/abc125/tasks/abc125_b
    /// </summary>
    public class QuestionA : AtCoderQuestionBase
    {
        public override IEnumerable<object> Solve(TextReader inputStream)
        {
            var n = inputStream.ReadInt();
            var values = inputStream.ReadIntArray();
            var costs = inputStream.ReadIntArray();
            var diff = values.Zip(costs, (v, c) => v - c).Where(d => d > 0).Sum();

            yield return diff;
        }
    }
}

namespace Yorukatsu057
{
    class Program
    {
        static void Main(string[] args)
        {
            IAtCoderQuestion question = new QuestionA();    // 問題に合わせて書き換え
            var answers = question.Solve(Console.In);
            foreach (var answer in answers)
            {
                Console.WriteLine(answer);
            }
        }
    }
}

#region Base Classes

namespace Yorukatsu057.Questions
{

    public interface IAtCoderQuestion
    {
        IEnumerable<object> Solve(string input);
        IEnumerable<object> Solve(TextReader inputStream);
    }

    public abstract class AtCoderQuestionBase : IAtCoderQuestion
    {
        public IEnumerable<object> Solve(string input)
        {
            var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
            var reader = new StreamReader(stream, Encoding.Unicode);

            return Solve(reader);
        }

        public abstract IEnumerable<object> Solve(TextReader inputStream);
    }

}

#endregion

#region Extensions

namespace Yorukatsu057.Extensions
{
    internal static class TextReaderExtensions
    {
        internal static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
        internal static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
        internal static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
        internal static string ReadString(this TextReader reader) => reader.ReadLine();

        internal static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
        internal static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
        internal static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
        internal static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
    }
}

#endregion

Measured memory_bytes: 13524
#include<bits/stdc++.h>
using namespace std;
#define EPS (1e-10)
static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

struct Point{
  double x,y;
  Point(){}
  Point(double x,double y):x(x),y(y){}
  Point operator+(Point p){return Point(x+p.x,y+p.y);}
  Point operator-(Point p){return Point(x-p.x,y-p.y);}
  Point operator*(double k){return Point(x*k,y*k);}
  Point operator/(double k){return Point(x/k,y/k);}

};

struct Segment{
  Point p1,p2;
  int o,l;
  Point c;
  double x;
  bool operator<(const Segment &s)const{
    return x < s.x;
  }
};

typedef Point Vector;

double norm(Vector a){
  return a.x*a.x+a.y*a.y;
}

double abs(Vector a){
  return sqrt(norm(a));
}


double dot(Vector a,Vector b){
  return a.x*b.y+a.y*b.x;
}

double cross(Vector a,Vector b){
  return a.x*b.y-a.y*b.x;
}

int ccw(Point p0, Point p1, Point p2){
  Vector a = p1-p0;
  Vector b = p2-p0;
  if(cross(a,b) > EPS ) return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS ) return CLOCKWISE;
  if(dot(a,b) < -EPS ) return ONLINE_BACK;
  if(norm(a) < norm(b) ) return ONLINE_FRONT;
  
  return ON_SEGMENT;
}

bool intersect(Point p1,Point p2,Point p3,Point p4){
  return (ccw(p1,p2,p3) * ccw(p1,p2,p4) <= 0 &&
	  ccw(p3,p4,p1) * ccw(p3,p4,p2) <= 0 );
}

bool intersect(Segment s1, Segment s2){
  return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}

Point getCrossPoint(Segment s1,Segment s2){
  Vector base = s2.p2 - s2.p1;
  double d1 = abs(cross(base,s1.p1-s2.p1));
  double d2 = abs(cross(base,s1.p2-s2.p1));
  double t = d1 / (d1+d2);
  return s1.p1 + (s1.p2-s1.p1) * t;
}

int main(){
  int t;cin >> t;
  while(t--){
    Segment r;
    cin >> r.p1.x >> r.p1.y >> r.p2.x >> r.p2.y;
    int n;cin>>n;
    int i,j,k;
    vector<Segment> vs;vs.clear();
    Segment seg;
    for(i=0;i<n;i++){
      cin >> seg.p1.x >> seg.p1.y >> seg.p2.x >> seg.p2.y >> seg.o >> seg.l;
      if(intersect(r,seg)) {
	seg.x = abs(getCrossPoint(r,seg)-r.p1);
	vs.push_back(seg);
      }
    }
    sort(vs.begin(),vs.end());
    int num = vs.size();
    //cout << num << endl;
    //for(i=0;i<num;i++) cout << vs[i].x << endl;

    int inf = 1 << 20;
    int o = inf;
    
    int dp[105][2]={{}};
    fill(dp[0],dp[105],inf);
    
    dp[0][0]=0;dp[0][1]=0;

    for(i=0;i<num;i++){
      if(vs[i].o==1&&vs[i].l==0){
	dp[i+1][0] = min(dp[i][0],dp[i][1]+1);
      }else if(vs[i].o==1&&vs[i].l==1){
	dp[i+1][1] = min(dp[i][0]+1,dp[i][1]);
      }else if(vs[i].o==0&&vs[i].l==0){
	dp[i+1][1] = min(dp[i][0]+1,dp[i][1]);
      }else if(vs[i].o==0&&vs[i].l==1){
	dp[i+1][0] = min(dp[i][0],dp[i][1]+1);
      }
      
    }
    o=min(dp[num][0],dp[num][1]);
    cout << o << endl;
  }
  return 0;
}

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

typedef long long ll;
using namespace std;

int n,x;
int a[105];

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

	cin >> n >> x;
	for (int i = 0;i < n;i++){
		cin >> a[i];
	}
	sort(a,a+n);
	
	int sum = 0;

	int ans = 0;

	for (int i = 0;i < n;i++){
		sum += a[i];
		if(sum == x){ans = i+1; break;}
		else if(sum > x){ans = i; break;}
		if(i == n-1)ans = n-1;
	}	

	cout << ans << endl;

	return 0;

}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int h,m,f[1440] = {0},n,i,j,y=0;
	for(i = 1;i <= 2;i++){
		scanf("%d",&n);
		for(j = 1;j <= n;j++){
			scanf("%d%d",&h,&m);
			f[h*60+m] = 1;
		}
	}
	for(i = 0;i <= 1439;i++){
		if(f[i]){
			if(y) printf(" ");
			printf("%d:%02d",i/60,i%60);
			y = 1;
		}
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 620
#include <iostream>
#include <cstdio>

using namespace std;

int mn = 2e9;
string s;

int main()
{
    cin>>s;
    mn = s.size();
    for(int i = 1; i < s.size(); i++)
    {
        if(s[i] != s[i - 1])
        {
            mn = min(mn, max((int)s.size() - i, i));
        }
    }
    printf("%d", mn);
    return 0;
}


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

int main() {
    int k;
    cin >> k;

    int ans = 0;
    for (int i = 1; i < k; i++) {
        ans += ((k - i + 1) / 2);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int yes=0,a,b,A,B,C;
	double n=2,c;
	cin >> n;
	for (a = (int)(n / 4) + 1; a <= 3500; a++)
	{
		if (yes)break;
			for (b = (int)(n*a / (4 * a - n)) + 1; b <= 3500; b++)
			{
				c = n*a*b / (4 * a*b - n*b - n*a);
				if (c <= 3500 && (int)c == c) {
					yes = 1;
					A = a;
					B = b;
					C = c;
					break;
				}
			}
	}

	cout << A <<" "<< B <<" "<< C << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;

const int N = 100100;

ll a[N], b[N];
vector<pair<int, int>> g[N];
int used[N];

void dfs(int v, int from = -1) {
    used[v] = 1;
    for (auto p : g[v]) {
        if (used[p.first]) {
            continue;
        }
        dfs(p.first, p.second);
    }
    ll t = 0;
    for (auto p : g[v]) {
        if (p.second != from) {
            t += b[p.second];
        }
    }
    if (v == 1) {
        if (t != a[1] + a[1] * (g[v].size() > 1)) {
            cout << "NO";
            exit(0);
        }
        return;
    }
    if (g[v].size() == 1) {
        b[from] = a[v];
    } else {
        if (t > 2 * a[v]) {
            cout << "NO";
            exit(0);
        }
        b[from] = 2 * a[v] - t;
    }
}

void check(int v) {
    used[v] = 1;
    for (auto p : g[v]) {
        if (!used[p.first]) {
            check(p.first);
        }
    }
    if (g[v].size() == 1) {
        return;
    }
    ll t = 0;
    ll m = 0;
    for (auto p : g[v]) {
        t += b[p.second];
        m = max(m, b[p.second]);
    }
    if (t % 2 || m > t / 2) {
        cout << "NO";
        exit(0);
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int t1, t2;
        cin >> t1 >> t2;
        g[t1].push_back({t2, i});
        g[t2].push_back({t1, i});
    }
    dfs(1);
    for (int i = 1; i <= n; ++i) {
        used[i] = 0;
    }
    check(1);
    cout << "YES";
    return 0;
}

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

#define MOD (1000000000+7)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;
#define forf(i,a,b) for(int i = (a); i < (b); i++)
#define forr(i,a,b) for(int i = (a); i > (b); i--)
#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];

// template starts
typedef long long int ll;
ll fact(ll n, ll p){
	ll ans = 1;
	for(ll i = 1; i <= n; i++){
		ans *= i;
		ans %= p;
	}
	return ans;
}
ll power(ll x, ll n, ll p){
	ll res = 1;
	if(n == 0) return 1;
	if(n == 1) return x%p;
	if(n%2 == 1) res = x%p;

	ll temp = power(x,n/2,p);
	return res*((temp*temp)%p)%p;
}
ll inv(ll a, ll p){
	return power(a,p-2,p);
}
ll nCr(ll n, ll r, ll p){
	if(r > n) return 0;
	ll t1 = fact(n,p);
	ll t2 = inv(fact(r,p),p);
	ll t3 = inv(fact(n-r,p),p);

	return (((t1*t2)%p)*t3)%p;
}
vector<vector<ll> > multiply(vector<vector<ll> > &a, vector<vector<ll> > &b, ll p){
	int r1,c1,r2,c2;
	r1 = a.size(); c1 = a[0].size();
	r2 = b.size(); c2 = b[0].size();

	vector<vector<ll> > result(r1,vector<ll>(c2,0));

	if(c1 != r2) return result;

	for(int i = 0; i < r1; i++){
		for(int j = 0; j < c2; j++){
			for(int k = 0; k < c1; k++){
				result[i][j] += a[i][k]*b[k][j];
				result[i][j] %= p;
			}
		}
	}
	return result;
}
vector<vector<ll> > power(vector<vector<ll> >&a,ll n, ll p){
	int r = a.size();
	vector<vector<ll> > result(r,vector<ll>(r,0));
	for(int i = 0; i < r; i++) result[i][i] = 1;

	while(n > 0){
		if(n%2 == 1){
			result = multiply(result,a,p);
		}
		n /= 2;
		a = multiply(a,a,p);
	}
	return result;
}
// template ends here

double pi = acos(-1);

void solve(){
	// code starts from here
	ll A,B,H,M;
	double ans = 0;
	cin >> A >> B >> H >> M;
	
	M = M + 60*H;
	
	double min = M%60, hr = M%3600;
	double dmin = 6.0*min, hrmin = 0.5*hr;
	double diff = dmin-hrmin;
	double co = cos(diff*pi/180.0);
	
	ans = A*A + B*B - 2*A*B*co;
	ans = sqrt(ans);
	cout <<setprecision(20)<< ans << endl;
	
	
	
}

int main(){
 	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	int T;
	T = 1;
	while(T--){
		solve();
	}

	return 0;
}


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

int main(){
    int N;
    cin >> N;
 
  	for(int i=0;i<N;i++){
      int x,y,b,p;
      cin >> x >> y >> b >> p;
      
      if(p<2&&b>=5&&x*b+y*p>=(x*b+y*2)*0.8){
       cout << (x*b+y*2)*0.8 << endl;
    }
    else if(b<5&&p>=2&&x*b+y*p>=(x*5+y*p)*0.8){
       cout << (x*5+y*p)*0.8 << endl;
    }
    else if(b<5&&p<2&&x*b+y*p>=(x*5+y*2)*0.8){
       cout << (x*5+y*2)*0.8 << endl;
    }      
    else if(b>=5&&p>=2){
       cout << (x*b+y*p)*0.8 << endl;
    }  
    else{
      cout << x*b+y*p << endl;
    }
    }
  return 0;
}


Measured memory_bytes: 3240
#include <cstdio>

long long A, B, C, K;
long long res;

void solve()
{
	if(K%2==0){
		res = A-B;
	}
	else
		res = B-A;
	printf("%lld\n", res);
}

int main()
{
	scanf("%lld %lld %lld %lld", &A, &B, &C, &K);
	solve();
	return 0;
}

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

using namespace std;

int l;
char s[15];
long long res;

long long sum(int l, int r){
	long long val = 0;
	for(int ii = l; ii <= r; ii++)
	val = val * 10 + (s[ii] - '0');
	return val;
}

void solve(int lv, int p, long long s){
	if(lv == l - 1){
		res += (s + sum(p, l - 1));
		return;
	}
	solve(lv + 1, lv + 1, s + sum(p, lv));
	solve(lv + 1, p, s);
}

int main(){
	scanf("%s", &s);
	l = strlen(s);
	solve(0, 0, 0);
	printf("%lld\n", res);
}


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

int main(){
    string s;
    cin>>s;
    int f=0;
    for(int i=0;i<s.size()-1;i++){
    	if(s[i+1]==s[i]){
    		f=1;
    	}
    }
    if(f==1){
    	cout<<"Bad"<<endl;
    }
    else{
    	cout<<"Good"<<endl;
    }
   return 0;
}

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

using namespace std;

#define rep(i, n) for(long int i = 0; i < n; i++)
#define P pair<int, int>
#define ll long long
typedef vector<int> vec;
typedef vector<vec> mat;

int main(){
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    ll N = in<ll>(),A = in<ll>(),B = in<ll>();
    ll amari = N % (A+B);
    ll count = N / (A+B);
    cout << count * A + min(A,amari) << "\n";
}

Measured memory_bytes: 256
#include<stdio.h>
#define LEN 20001
#define AREA 10001

typedef struct Distritc{
    int j;
    int s;
}distritc;

int main(void){
    int i, j = 0, k = 0, s, sum = 0;
    char slash;
    int s1[LEN];
    distritc s2[AREA];
    
    for(i = 0; scanf("%c", &slash) != EOF; i++){
        if(slash == '\\') s1[j++] = i;
        else if(slash == '/' && j > 0){
            s = i - s1[--j];
            sum += s;
            
            while(k > 0 && s2[k - 1].j > j){s += s2[--k].s;}
            s2[k].j = j; s2[k++].s = s;
        }
    }
    
    printf("%d\n", sum);
	if(!k) printf("%d\n", k);
	else printf("%d", k);
    for(i = 0; i < k; i++) {
        printf(" %d", s2[i].s);
        if(i == k - 1)printf("\n");
    };
    
    
    return 0;
}


Measured memory_bytes: 2140
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] d = new int[N];
    for(int i=0;i<N;i++){
      d[i] = sc.nextInt();
    }
    int ans = 0;
    for(int i=0;i<N-1;i++){
      for(int j=i+1;j<N;j++){
        ans+=d[i]*d[j];
      }
    }
    System.out.println(ans);
  }
}

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

using namespace std;

int main()
{
    vector<int> vec(3);
    for (int i = 0; i < 3; ++i)
        cin >> vec[i];

    int k;
    cin >> k;

    int max_index = 0;
    for (int i = 1; i < 3; ++i) {
        if (vec[max_index] < vec[i])
            max_index = i;
    }

    for (int i = 0; i < k; ++i)
        vec[max_index] *= 2;

    cout << vec[0] + vec[1] + vec[2] << '\n';
}


Measured memory_bytes: 888
#include <iostream>

using namespace std;

int main()
{
   string s,t;
   cin >> s >> t;
   int l,m,i,flag=1;
   l = s.length();
   m = t.length();
   if(l==(m-1)){
       for(i=0;i<l;i++){
           if(s[i]!=t[i]){
               flag =0;
               break;
           }
       }
       if(flag==1) cout << "Yes";
       else cout << "No";
       
   }
   else cout <<"No";
   
   return 0;
}

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

int main() {
	ll A, B, K;
	cin >> A >> B >> K;
	ll takahashi;
	ll aoki;
	if (K <= A) {
		takahashi = A - K;
		aoki = B;
	}
	else if (K <= A + B) {
		takahashi = 0;
		aoki = B - (K - A);
	}
	else{
		takahashi = 0;
		aoki = 0;
	
	}
	cout << takahashi << " " << aoki << endl;
	//cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3568
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <queue>

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

using namespace std;

void bfs(vector<vector<uint64_t>>& tb, int i, int j, int h, int w) {
  queue<pair<int,int>> q;
  q.push(make_pair(i,j));
  while(!q.empty()){
    auto p=q.front();q.pop();
    int y=p.first;
    int x=p.second;
    if(tb[y][x] == 1) continue;
    uint64_t val = tb[y][x];
    tb[y][x] = 1;
    int dy[] = {1,0,-1,0};
    int dx[] = {0,1,0,-1};
    REP(k,4){
      int ny=y+dy[k];
      int nx=x+dx[k];
      if(ny<0||nx<0||ny>=h||nx>=w) continue;
      if(tb[ny][nx]==val){
        q.push(make_pair(ny,nx));
      }
    }
  }
}

int main() {
  while(1){
    int n;
    cin >> n;
    if(!n) break;
    vector<int> xa;
    vector<int> ya;
    xa.push_back(-1);
    ya.push_back(-1);
    vector<int> x1(n);
    vector<int> y1(n);
    vector<int> x2(n);
    vector<int> y2(n);
    REP(i,n){
      cin >> x1[i] >> y2[i] >> x2[i] >> y1[i];
      xa.push_back(x1[i]);
      xa.push_back(x2[i]);
      ya.push_back(y1[i]);
      ya.push_back(y2[i]);
    }
    sort(begin(xa),end(xa));
    auto xi = unique(begin(xa),end(xa));
    xa.resize(xi-begin(xa));
    sort(begin(ya),end(ya));
    auto yi = unique(begin(ya),end(ya));
    ya.resize(yi-begin(ya));
    vector<vector<uint64_t>> tb(ya.size(), vector<uint64_t>(xa.size()));
    REP(i,n){
      int bx=lower_bound(begin(xa),end(xa),x1[i]) - begin(xa);
      int ex=lower_bound(begin(xa),end(xa),x2[i]) - begin(xa);
      int by=lower_bound(begin(ya),end(ya),y1[i]) - begin(ya);
      int ey=lower_bound(begin(ya),end(ya),y2[i]) - begin(ya);
      for(int j=by;j < ey;++j){
        for(int k=bx;k < ex;++k){
          tb[j][k] += UINT64_C(1) << (i+1);
        }
      }
    }
    int cnt = 0;
    REP(i,ya.size()){
      REP(j,xa.size()){
        if(tb[i][j] != 1) {
          cnt++;
          bfs(tb,i,j,ya.size(),xa.size());
        }
      }
    }
    cout << cnt << endl;
  }
  return 0;
}

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

using namespace std;

struct A {
    vector<int> hs, ws;
    A() {}
    A(int max_height, int max_width): ws(max_height, 0), hs(max_width, 0) {}    
    void normalize() {
        int cur = 0;
        for (int i = (int) ws.size() - 1; i >= 0; --i) {
            for (int j = cur; j < ws[i]; ++j) {
                hs[j] = max(hs[j], i + 1);
            }
            cur = ws[i];
        }
        
        cur = 0;
        for (int j = (int) hs.size() - 1; j >= 0; --j) {
            for (int i = cur; i < hs[j]; ++i) {
                ws[i] = max(ws[i], j + 1);
            }
            cur = hs[j];
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    vector<vector<int>> board(h, vector<int>(w, 0));
    vector<vector<int>> board_sum(h + 1, vector<int>(w + 1, 0));
    for (int i = 0; i < h; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < w; ++j) {
            board[i][j] = s[j] == '#';
            board_sum[i+1][j+1] = board[i][j] + board_sum[i][j+1] + board_sum[i+1][j] - board_sum[i][j];
        }
    }
    
    auto all_equal = [&](int i, int j, int h0, int w0) {
        if (i + h0 > h || j + w0 > w) return false;
        int area = h0 * w0;
        int rect_sum = board_sum[i + h0][j + w0] - board_sum[i][j + w0] - board_sum[i + h0][j] + board_sum[i][j];
        return rect_sum == 0 || rect_sum == area;
    };
    
    vector<vector<A>> cur(h, vector<A>(w));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cur[i][j] = A(h - i, w - j);
            while (all_equal(i, j, 1, cur[i][j].ws[0] + 1)) {
                ++cur[i][j].ws[0];
            }
            for (int k = 1; k < h - i; ++k) {
                cur[i][j].ws[k] = cur[i][j].ws[k-1];
                while (!all_equal(i, j, k + 1, cur[i][j].ws[k])) {
                    --cur[i][j].ws[k];
                }
            }
            cur[i][j].normalize();
        }
    }
    
    int complexity = 0;
    while (cur[0][0].ws[h - 1] < w) {
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                // Splitting vertically
                for (int k = 0; k < h - i; ++k) {
                    int j0 = j + cur[i][j].ws[k];
                    if (j0 >= w) continue;
                    cur[i][j].ws[k] += cur[i][j0].ws[k];
                }
                
                // Splitting horizontally
                for (int l = 0; l < w - j; ++l) {
                    int i0 = i + cur[i][j].hs[l];
                    if (i0 >= h) continue;
                    cur[i][j].hs[l] += cur[i0][j].hs[l];
                }
                
                cur[i][j].normalize();
            }
        }
        ++complexity;
    }

    cout << complexity << endl;

    return 0;
}


Measured memory_bytes: 29952
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef string str;
typedef std::pair<ll,ll> pl;
typedef std::map<string, ll> msl;
typedef std::map<ll, ll> mll;
typedef std::vector<ll> vl;
typedef std::vector<pl> vpl;
const long double EPS = 1e-9;

#define rep(i, n) for(ll (i) = 0; (i) < (n) ; (i)++ )
#define For(i, a, b) for(ll (i) = (a); (i) < (b) ; (i)++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define tol(c) char((c)+0x20)
#define tou(c) char((c)-0x20)
#define pb push_back
#define mp make_pair
#define pr(a) cout << (a)
#define prl(a) cout << (a) << endl
#define prl2(a,b) cout << (a) << " " << (b) << endl
#define prs(a) cout << (a) << " "
#define yn(condition) if ((condition)) prl("Yes"); else prl("No");
#define YN(condition) if ((condition)) prl("YES"); else prl("NO");
#define rpr(i,n,ans) rep((i),(n)) prs((ans[(i)]))
#define cpr(i,n,ans) rep((i),(n)) prl((ans[(i)]))
#define in1(a) cin >> (a)
#define in2(a,b) cin >> (a) >> (b)
#define in3(a,b,c) cin >> (a) >> (b) >> (c)
#define in4(a,b,c,d) cin >> (a) >> (b) >> (c) >> (d)
#define rin1(i,n,a) rep((i),(n)) cin >> (a[(i)])
#define rin2(i,n,a,b) rep((i),(n)) cin >> (a[(i)]) >> (b[(i)])
#define rin3(i,n,a,b,c) rep((i),(n)) cin >> (a[(i)]) >> (b[(i)]) >> (c[(i)])
#define e1 first
#define e2 second
#define ctol(c) ll((c)) - ll('0')
#define ltos(n) to_string((n))
#define items(kv, v) for(auto &(kv): (v))
#define ndig(N, n) ctol(ll(ltos((N))[ll(ltos((N)).length()) - (n)]))
#define beto(a,b,c) (a) < (b) && (b) < (c)
#define betc(a,b,c) (a) <= (b) && (b) <= (c) 
#define rsort(a,n) sort(a,a+n,greater<>())
#define Forchar(c,a,z) for(char (c) = (a); (c) <= (z); (c)++) 
#define cntchar(s,c) count(all((s)), c)

const ll mod = 1e9 + 7;
const ll INF = mod * mod;
const ll MAX_N = 100000;

int main(void){
    ll a, b;
    str s,t;
 
    in1(s);
    Forchar(c,'a','z') if (cntchar(s,c) == 0) {prl(c); return 0;}
    prl("None");
 
    return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <vector>
#include <set>
#include <map>
using namespace std;
long long solve(const vector<pair<pair<int,int>,pair<int,int>>> &v){
	set<int>lx,ly;
	for(auto &e:v){
		lx.insert(e.first.first);lx.insert(e.second.first);
		ly.insert(e.first.second);ly.insert(e.second.second);
	}
	int i;
	map<int,int>mx,my,sx,sy;
	i=0;for(auto ix1=lx.begin(),ix2=lx.begin();++ix2!=lx.end();++ix1,++i){
		mx[*ix1]=i,sx[i]=*ix2-*ix1;
	}
	mx[*lx.rbegin()]=i,sx[i]=0;
	i=0;for(auto iy1=ly.begin(),iy2=ly.begin();++iy2!=ly.end();++iy1,++i){
		my[*iy1]=i,sy[i]=*iy2-*iy1;
	}
	my[*ly.rbegin()]=i,sy[i]=0;
	vector<vector<int>>m(my.size());
	for(auto &e:m)e.resize(mx.size());
#if 0
	for(auto &e:v){
		for(int x=mx[e.first.first];x<mx[e.second.first];x++)
			for(int y=my[e.first.second];y<my[e.second.second];y++)m[y][x]=1;
	}
#else
	for(auto &e:v){
		m[my[e.first.second]][mx[e.first.first]]++;
		m[my[e.second.second]][mx[e.first.first]]--;
		m[my[e.first.second]][mx[e.second.first]]--;
		m[my[e.second.second]][mx[e.second.first]]++;
	}
	for(int x=1;x<sx.size();x++)for(int y=0;y<sy.size();y++)m[y][x]+=m[y][x-1];
	for(int x=0;x<sx.size();x++)for(int y=1;y<sy.size();y++)m[y][x]+=m[y-1][x];
#endif
	long long r=0;
	for(int x=0;x<sx.size();x++)for(int y=0;y<sy.size();y++)if(m[y][x])r+=(long long)sx[x]*sy[y];
	return r;
}
int main(){
	int N,x1,y1,x2,y2;
	vector<pair<pair<int,int>,pair<int,int>>>v;
	set<int>lx,ly;
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		v.push_back({{x1,y1},{x2,y2}});
	}
	printf("%lld\n",solve(v));
}

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

using namespace std;
const int N=5e5+5;
int a[N];
long long solve(long long n)
{
    if(n==1) return 1;
    return 1+2*solve(n/2);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    long long n;
    cin>>n;
    cout<<solve(n)<<endl;
    return 0;
}


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

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

  int N;
  string S;
  cin >> N >> S;
  if(N % 2 == 1){
    cout << "No" << endl;
    return 0;
  }
  int M = N/2;
  bool ans= true;
  for(int i=0;i<M;i++){
    if(S[i] != S[i+M]){
      ans = false;
    }
  }
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

int main(){
	int m,f,r;
	
	while(1){
		cin>>m>>f>>r;
		if(m==-1&&f==-1&&f==-1)break;
		if(m==-1||f==-1)cout<<'F'<<endl;
		else if(m+f>=80)cout<<'A'<<endl;
		else if(m+f>=65)cout<<'B'<<endl;
		else if(m+f>=50)cout<<'C'<<endl;
		else if(m+f>=30&&r>=50)cout<<'C'<<endl;
		else if(m+f>=30)cout<<'D'<<endl;
		else cout<<'F'<<endl;
	}	
}


Measured memory_bytes: 3096
#ABC118B-FoodsLovebyEveryone.py

from sys import stdin

N, M = list(map(int, stdin.readline().split()))

kind = 0
box = []
for i in range(M):
    box.append(0)

for j in range(N):
    box1 = list(map(int, stdin.readline().split()))
    for i in range(box1[0]):
        box[box1[i+1]-1] += 1
count = 0

for i in range(M):
    if box[i] == N:
        count += 1

print(count)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ALL(A) A.begin(),A.end()
const long long mod=1000000007;
int main(){
    int n;string s;
    cin>>n;
    cin>>s;
    int w[n+2],e[n+2];
    w[0]=0;e[0]=0;w[n+1]=0;e[n+1]=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='E')
        w[i+1]=w[i];
        else
        w[i+1]=w[i]+1;
        if(s[n-i-1]=='E')
        e[n-i]=e[n-i+1]+1;
        else
        e[n-i]=e[n-i+1];
    }
    int ans=e[2]+w[0];
    for(int i=2;i<=n;i++)
    {
        ans=min(ans,w[i-1]+e[i+1]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3076
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {

    int N;
    cin >> N;
    vector<long long> A(N);
    rep(i,N) {
        cin >> A[i];
    }

    vector<long long> one(61), zero(61);
    rep(i,61) {
        one[i] = 0;
        zero[i] = 0;
    }

    long long ans = 0;
    rep(i,N) {
        rep(j,61) {
            if(A[i]&(1ull<<j)) {
                ans = (ans + zero[j] * ((1ull<<j) % MOD) % MOD) % MOD;
                one[j]++;
            } else {
                ans = (ans + one[j] * ((1ull<<j) % MOD) % MOD) % MOD;
                zero[j]++;
            }
        }
    }

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

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

int main() {
  string str;
  cin >> str;
  string ans = "Yes";
  if (str.at(0) == str.at(1)) {
    ans = "No";
  } else if (str.at(1) == str.at(2)) {
    ans = "No";
  } else if (str.at(2) == str.at(0)) {
    ans = "No";
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
X=list(map(int, input().split())) 
X_max = max(X)
X_min = min(X)
 
answerlist = []
for i in range(X_min,X_max+1):
  newX = [(n-i)**2 for n in X]
  total = sum(newX)
  answerlist.append(total)
  
print(min(answerlist))
  


Measured memory_bytes: 38640
#include <iostream>
#include <vector>
#define PI 3.141592
using namespace std;


int main()
{
	//a
	/*int r;
	cin >> r;
	double l = (double)r * 2.0 * PI;

	printf("%.6f", l);

	return 0;*/


	//c
	int n;
	cin >> n;
	vector<int> count(n, 0);

	for (int i = 1; i < n; i++) {
		int tmp;
		cin >> tmp;
		tmp--;
		count[tmp]++;
	}

	for (int i = 0; i < n; i++) {
		printf("%d\n", count[i]);
	}


}



Measured memory_bytes: 4048
#include<iostream>

using namespace std;

int main() {
    int a,b,c,n;
    cin >> a>> b>> c>> n;
    
    int cnt =0;
    int cond;

    for(int i=0;i<n/a+1;i++){
       if(a*i > n) break;

        for(int j=0;j<n/b+1;j++){

           if(a*i+b*j > n) break;

            if((n- a*i -b*j) % c == 0) cnt++;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <map>

using namespace std;
using llong = long long;
const int MOD=1000000007;


int main(int argc, char**argv){
    vector<int> a(5);
    for (int i = 0; i < 5; i++){
        cin >> a[i];
    }
    int idx = 0;
    int min_val = 10;
    for (int i = 0; i < 5; i++){
        if (a[i]%10 == 0) continue;
        if (a[i] % 10 < min_val){
            idx = i;
            min_val = a[i] % 10;
        }
    }
    int ans = a[idx];
    for (int i = 0; i < 5; i++){
        if (i == idx) continue;
        if (a[i] % 10 != 0) ans += (a[i]/10 + 1) * 10;
        else ans += a[i];
    }
    cout << ans << endl;

    return 0;
}














Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <map>
#include <cmath>
#define MOD_P 1000000007
#define MOD_Q 998244353
#define PI 3.14159265358979
#define ll long long
using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> dp(n);
	for (int i = 0; i < n; i++) {
		cin >> dp[i];
	}

	for (int i = 0; i < n - k; i++) {
		printf("%s\n", dp[i] < dp[i + k] ? "Yes" : "No");
	}

	return 0;
}


Measured memory_bytes: 4024
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;

int main(int argc, char *argv[]) {

	int N,K; cin >> N >> K;

	if (N % K == 0) {
		cout << 0 << endl;
	}else {
		cout << 1 << endl;
	}
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}

vector<ll> vl;
int n;
string s;
string t;

int main(){
	cin >> n;
	cin >> s >> t;
	rep(i,s.size()){
		if(s[i] == t[i])vl.push_back(0);
		else{
			vl.push_back(1);
			i++;
		}
	}
	ll ans;
	if(vl[0] == 0)ans = 3;
	else ans = 6;
	rep(i,vl.size()-1){
		if(vl[i+1] == 1 && vl[i] == 1)ans = (ans * 3)%MOD;
		else if(vl[i+1] == 1 && vl[i] == 0)ans = (ans * 2)%MOD;
		else if(vl[i+1] == 0 && vl[i] == 0)ans = (ans * 2)%MOD;
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
import sys
N = int(input())
T = []
for _ in range(N):
	T.append(list(map(int,input().split())))

#--------------------------------------------
now = [0,0]
now_time = 0
for i in range(N):
  left_time = T[i][0] - now_time
  target = [T[i][1],T[i][2]]
  distance = abs(T[i][1]-now[0]) + abs(T[i][2]-now[1])
  if distance <= left_time and distance % 2 == left_time % 2:
    now_time = T[i][0]
    now = target
    
  else:
    print("No")
    sys.exit()

print("Yes")


Measured memory_bytes: 90288
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	string n;
	cin >> n;
	if (n[0] == '9' || n[1] == '9'){
		cout << "Yes" <<endl;
	}
	else{
		cout << "No" << endl;
	}
	return 0;
}

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  vector<int> deg(n);
  for (int _ = n - 1; _--; ) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
    ++deg[u], ++deg[v];
  }
  string s;
  cin >> s;
  if (s == string(n, 'B')) {
    cout << "0\n";
    exit(0);
  }
  queue<int> que;
  for (int v = 0; v < n; ++v) {
    if (deg[v] == 1 and s[v] == 'B') {
      que.push(v);
    }
  }
  vector<bool> be(n, true);
  while (not que.empty()) {
    int v = que.front();
    que.pop();
    be[v] = false;
    for (int u : g[v]) {
      if (be[u]) {
        --deg[v];
        --deg[u];
        if (deg[u] == 1 and s[u] == 'B') {
          que.push(u);
        }
        break;
      }
    }
  }
  int res = 0;
  vector<int> a(n);
  for (int v = 0; v < n; ++v) {
    if (be[v]) {
      res += deg[v];
      if (s[v] == 'W') {
        if (deg[v] % 2 == 0) {
          a[v] = deg[v] ? 2 : 0;
          ++res;
        }
      } else {
        if (deg[v] & 1) {
          a[v] = 2;
          ++res;
        }
      }
    }
  }
  vector<int> d(n);
  auto dfs = [&](auto&& self, int v, int p) -> void {
    for (int u : g[v]) {
      if (be[u] and u != p) {
        d[u] = d[v] + a[u];
        self(self, u, v);
      }
    }
  };
  int r = find(begin(be), end(be), true) - begin(be);
  for (int _ = 2; _--; ) {
    d[r] = a[r];
    dfs(dfs, r, -1);
    r = max_element(begin(d), end(d)) - begin(d);
  }
  res -= d[r];
  cout << res << '\n';
}


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

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#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 FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

struct Point { LL x,y; };

bool cmp(const Point& a, const Point& b)
{
    return atan2(a.y,a.x) < atan2(b.y,b.x);
}

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    int n;
    while (cin >> n) {
        vector<Point> A(n);
        FOR(i,0,n)
            cin >> A[i].x >> A[i].y;
        sort(ALL(A),cmp);
        FOR(i,0,n)
            A.push_back(A[i]);
        LL ans = 0;
        FOR(i,0,2*n) {
            LL x = 0, y = 0;
            FOR(j,i,min(2*n,i+n)) {
                x += A[j].x;
                y += A[j].y;
                ans = max(ans, x*x + y*y);
            }
        }
        cout.precision(12); cout << fixed << sqrt(ans) << endl;
    }
    return 0;
}


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

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

void solve (){
	int n;
	cin >> n;
	
	if(n %1000 == 0){
		cout << 0 << endl;
		return;
	}
	
	cout << (1000 - n % 1000) << endl;
}

int32_t main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	int tc = 1;
	//cin >> tc;
	while(tc--)
		solve();
}


Measured memory_bytes: 3584
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<vector>
#include<math.h>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
const long long mod = 1e9 + 7;
typedef long long ll;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int n;
int a[100000],b[100000],c[100000];
int main(){
    cin>>n;
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>b[i];
    rep(i,n) cin>>c[i];
    sort(a,a+n);
    sort(c,c+n);
    ll ans=0;
    rep(i,n){
        ll ac=(lower_bound(a,a+n,b[i])-a);
        ll cc=(n-(upper_bound(c,c+n,b[i])-c));
        ans+=ac*cc;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int A[1000000]={},cnt=0,N;
void isort(int g){
    for(int i=g;i<N;i++){
        int v=A[i];
        int j=i-g;
        while(j>=0 && A[j]>v){
            A[j+g]=A[j];
            j=j-g;
            cnt++;
        }
        A[j+g]=v;
    }
}
void ssort(){
    cnt=0;
    int G[1000000]={},p=0,m;
    for(m=1;3*m+1<N;m=3*m+1);
    while(m>0){
        G[p++]=m;
        m/=3;
    }
    if(p>100){
        p=100;
    }
    for(int i=0;i<p;i++){
        isort(G[i]);
    }
    cout<<p<<endl;
    for(int i=0;i<p;i++){
        if(i!=p-1){
            cout<<G[i]<<" ";
        }
        else{
            cout<<G[i]<<endl;
        }
    }
    cout<<cnt<<endl;
    for(int i=0;i<N;i++){
        cout<<A[i]<<endl;
    }
}
int main(){
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    ssort();
    return 0;
}


Measured memory_bytes: 10900
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main()
{
  int N; //本の数
  int M; //アルゴリズムの数
  int X; //アルゴリズムの理解度の目標値
  cin >> N >> M >> X;
  vector<int> C(N); //本の値段
  vector<vector<int>> A(N, vector<int>(M)); //理解度の上昇値
  for(int i = 0; i < N; i++){
    cin >> C[i];
    for(int j = 0; j < M; j++){
      cin >> A[i][j];
    }
  }
  vector<int> price_sum((1 << N), 0); //各パターン毎の値段の合計
  for(int bit = 0; bit < (1 << N); bit++){
    vector<int> skill_score(M, 0); //各アルゴリズムの理解度
    for(int i = 0; i < N; i++){
      if(bit & (1 << i)){
        price_sum[bit] += C[i];
        for(int j = 0; j < M; j++){
          skill_score[j] += A[i][j];
        }
      }
    }
    for(int k = 0; k < M; k++){
      if(skill_score[k] < X)  {
        price_sum[bit] = INF;
        break;
      }
    }
  }
  int result = *min_element(price_sum.begin(), price_sum.end());
  if(result == INF) cout << -1 << endl;
  else cout << result << endl;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main() {
    fastio
    
    ll N,W;
    cin>>N>>W;
    vector<pair<ll,ll>> w(N);
    for(ll i=0;i<N;i++){
        ll x,y;
        cin>>x>>y;
        w[i]={x,y};
    }
    ll sumv_max=0;
    for(ll i=0;i<N;i++){
        sumv_max+=w[i].second; 
    }
    ll inf = 10000000000;
    vector<ll> dp(sumv_max+1,inf);
    dp[0]=0;
    for(ll i=1;i<=N;i++){
        auto p = w[i-1];
        for(ll j=sumv_max;j>=p.second;j--){
            dp[j]=min(dp[j],p.first+dp[j-p.second]);
        }
    }
    ll i=sumv_max;
    while(W<dp[i]){
        i--;
    }
    cout<<i<<"\n";
    return 0;
}

Measured memory_bytes: 3988
n = int(input())
ST = [list(map(str, input().split())) for _ in range(n)]
X = input()

ans = 0
flag = False
for st in ST:
    a, b = st
    b = int(b)
    if X == a:
        flag = True
        continue
    
    if flag is True:
        ans += b
print(ans)

Measured memory_bytes: 3316
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
//const ll MOD = 1e9 + 7;
const ll MOD = 998244353;

const ll MAX = 1e9 + 5;

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

	mcf_graph<ll, int> g(2 * n + 2);
	int s = 2 * n;
	int t = s + 1;
	g.add_edge(s, t, n * k, MAX);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int a;
			cin >> a;
			g.add_edge(i, n + j, 1, MAX - a);

		}
	}

	for (int i = 0; i < n; i++) {
		g.add_edge(s, i, k, 0);
	}

	for (int i = 0; i < n; i++) {
		g.add_edge(n + i, t, k, 0);
	}

	g.flow(s, t, n * k);
	vector<string> ans(n, string(n, '.'));
	vector<mcf_graph<ll, int>::edge> e(g.edges());

	ll sum = 0;
	for (auto it = e.begin(); it != e.end(); it++) {
		int fr = it->from;
		int to = it->to;
		int fl = it->flow;

		if (fr == s || to == t || fl == 0) {
			continue;
		}

		sum += MAX - it->cost;

		ans[fr][to - n] = 'X';
	}
	cout << sum << endl;
	for (string ai : ans) {
		cout << ai << endl;
	}

}

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

int main() {
  long long x;
  cin >> x;
  int r500 = x / 500 * 2;
  int r5 = x % 500 / 5;
  cout << r500*500 + r5*5 << endl;
  return 0;
}


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

#define ioso ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define kholo freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
#define laglo cerr << "Ti : " << clock() * 1.0 / CLOCKS_PER_SEC  << endl;
#define endl '\n';
#define ll long long
map<long long, long long> k;
ll f(ll h) {
	if(k.count(h)) return k[h];
	else {
		if(h==1) return k[h]=1;
		else if(h==0) return k[h]=0;
		else return k[h] = (f((floor(h/2)))*2) + 1;
	}
}
int main() {
	ioso; //kholo;
	ll h; cin >> h;
	ll ans = f(h); 
	cout << ans << endl;
	//laglo;
}

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

int culc(int x, int y, int z){
  return (x+y)*(x+y) + (y+z)*(y+z) + (z+x)*(z+x);
}

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


  for(int time=1;time<N+1;time++){
    int count=0;
    int x=1,y=1,z=1;
    for(int i=1;culc(i,i,i)<2*time+1;i++){
      for(int j=i;culc(i,j,j)<2*time+1;j++){
        for(int k=j;culc(i,j,k)<2*time+1;k++){
          if(culc(i,j,k)==2*time){
            if(i==j){
              if(j==k){
                count=count+1;
              }
              else{
                count=count+3;
              }
            }
            else if(j==k){
              count = count+3;
            }
            else{
              count=count+6;
            }
          }
        }
      }
    }
    cout << count<< endl;
  }






}


Measured memory_bytes: 3424