akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace A
{
    class Program
    {
        public static void Main(string[] args)
        {
            var n = ReadLineIntSpilit();
            var re = "safe";

            if(n[1] - n[2] >= 0) {
                re = "delicious";
            }else if(n[2]-n[1] > n[0]) {
                re = "dangerous";
            }

            Console.WriteLine(re);
            ReadLine();
        }

        /// <summary>
        /// stringを一文字ずつintにキャストして配列に変換します。
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        public static int[] StringCharArrayIntArray(string str)
        {
            List<int> b = new List<int>();
            for (int i = 0; i < str.Length; i++) {
                b.Add( int.Parse(str[i].ToString()));
            }
            return b.ToArray();
        }

        public static string ReadLine()
        {
            return Console.ReadLine();
        }

        public static int ReadLineInt()
        {
            return int.Parse(Console.ReadLine());
        }

        public static string[] ReadLineStringSplit(char a = ' ')
        {
            return ReadLine().Split(a).ToArray();
        }

        public static int[] ReadLineIntSpilit(char a = ' ')
        {
            return ReadLine().Split(a).Select(x => int.Parse(x)).ToArray();
        }
    }
}

Measured memory_bytes: 13396
#include <stdio.h>
#include <stdlib.h>

int main( int argc, char *argv[] )
{
    int n, m;
    int a;

    scanf( "%d %d", &n, &m );
    for( int i=0; i<m; i++ ) {
        scanf( "%d", &a );
        n -= a;
    }

    if( n < 0 ) n = -1;

    printf( "%d\n", n );
}


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

bool hit(string s,string t) {
  for(int i=0; i<s.length(); ++i) {
    if(s.at(i) == '*') continue;
    if(s.at(i) != t.at(i)) return false;
  }
  return true;
}

int main() {
  int n,m;
  while(cin>>n>>m, n|m) {
    vector< pair<string,int> > hlot;
    string s;
    int h;
    for(int i=0; i<n; ++i) {
      cin>>s>>h;
      hlot.push_back(pair<string,int>(s,h));
    }
    vector<string> have;
    for(int i=0; i<m; ++i) {
      cin>>s;
      have.push_back(s);
    }

    long long sum = 0;
    for(int i=0; i<n; ++i)
      for(int j=0; j<m; ++j)
        if(hit(hlot[i].first,have[j])) sum += hlot[i].second;

    cout<<sum<<endl;
  }
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    vector<ll> length(1005, 0);
    for(int i=0; i<N; i++)
    {
        int l;
        cin >> l;
        length[l]++;
    }

    vector<ll> cum(2005, 0);
    cum[0] = length[0];
    for(int i=1; i<2005; i++)
    {
        if(i < 1005) cum[i] = cum[i-1] + length[i];
        else cum[i] = cum[i-1];
    }

    ll ans = 0;
    for(int i=1; i<=1000; i++)
    {
        for(int j=i; j<=1000; j++)
        {
            ll sun;
            if(i==j)
            {
                sun = length[i] * (length[i]-1) * (length[i]-2) / 6;
                sun += length[i] * (length[i]-1) / 2 * (cum[i+j-1] - cum[i]);
            }
            else
            {
                sun = length[i] * length[j] * (length[j]-1) / 2;
                sun += length[i] * length[j] * (cum[i+j-1] - cum[j]);
            }
            ans += sun;
            // if(sun != 0) cout << "i:" << i << ", j:" << j << ", sun:" << sun << endl;
        }
    }
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cassert>
#include <cmath>
#include <complex>
#include <vector>
#include <utility>
using namespace std;

typedef complex<double> Point;
#define X real()
#define Y imag()
#define EPS 10e-8

namespace std {
  bool operator < (Point a, Point b) {
    if (a.X != b.X) return a.X < b.X;
    return a.Y < b.Y;
  }
}

double cross(Point a, Point b) {
  return (conj(a)*b).Y;
}

double dot(Point a, Point b) {
  return (conj(a)*b).X;
}

double dist2(Point a, Point b) {
  return dot(a-b, a-b);
}

struct Line : public vector<Point> {
  Line(Point a, Point b) {push_back(a); push_back(b);}
};

int n;
Point ps[3];

Line PerpendBisect(Line l) {
  Point mid = (l[0]+l[1])/2.0;
  return Line(mid, mid+(l[1]-l[0])*Point(0, 1));
}

Point GetCrossPoint(Line l, Line m) {
  double A = cross(l[1]-l[0], m[1]-m[0]);
  double B = cross(l[1]-l[0], l[1]-m[0]);
  if (abs(A) < EPS && abs(B) < EPS) return m[0];
  if (abs(A) < EPS) assert(false);
  return m[0] + B / A * (m[1]-m[0]);
}

double round3(double t) {
  return round(t*1000)/1000.0;
}

int main() {
  scanf("%d", &n);
  while (n--) {
    for (int i=0; i<3; i++) {
      double x, y;
      scanf("%lf%lf", &x, &y);
      ps[i] = Point(x, y);
    }

    Line l(ps[0], ps[1]);
    Line m(ps[1], ps[2]);
    Point p = GetCrossPoint(PerpendBisect(l), PerpendBisect(m));
    double r = sqrt(dist2(p, ps[0]));
    printf("%.3f %.3f %.3f\n", round3(p.X), round3(p.Y), round3(r));
  }
}

Measured memory_bytes: 2760
#include <iostream>
using namespace std;
const long long MOD = (1e9)+7;

long long mod_inv(long long x){
  long long ret = 1, k = x, t = MOD-2;
  while(t > 0){
    if(t&1){
      ret *= k;
      ret %= MOD;
    }
    k *= k;
    k %= MOD;
    t /= 2;
  }
  return ret;
}

long long conv(long long n, long long k){
  long long ret = 1, t = 1;
  for(int i = 0; i < k; ++i){
    ret *= (n-i);
    ret %= MOD;
    t *= (i+1);
    t %= MOD;
  }
  ret *= mod_inv(t);
  ret %= MOD;
  return ret;
}

int main(){
  int N, M;
  cin >> N >> M;
  long long ans = 1, k = M;
  for(int i = 2; i*i <= M; ++i){
    long long t = 0;
    while(k%i == 0){
      k /= i;
      ++t;
    }
    ans *= conv(N+t-1,t)%MOD;
    ans %= MOD;
  }
  if(k > 1){
    ans *= conv(N,N-1)%MOD;
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
/*
Author : farhan132
*/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef pair<ll , ll> lli;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;
typedef vector<lli> vlli;
typedef pair < ll , pair < ll , ll > > cm;

#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define PI 3.14159265359
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)
#define clean cout.flush()

const ll mod = (ll)1e9+7;
const ll maxn = (ll)1e5+10;
const int nnn = 664579+500;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = 1e18;

ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};

//ofstream wr ("txt.txt");
//ifstream rr ("input.txt");


void solve(){
	
	ll n;
	cin >> n;
	char a[n+5];
	ll dp1[n+5] , dp2[n+5];
	dp1[0] = 0;
	dp2[0] = 0;
	f1(n){
		cin >> a[i];
		dp1[i] = 0;
		dp2[i] = 0;
		if(a[i] == 'R') dp1[i] = 1;
		else dp2[i] = 1;
		dp1[i] += dp1[i-1];
		dp2[i] += dp2[i-1];
	}
	dp1[n+1] = dp1[n];
	dp2[n+1] = dp2[n];
	ll ans = INF;
	for(ll i = 1; i <= n+1; i++){
		ans = min(ans , dp2[i-1]+(dp1[n]-dp1[i-1]) - min(dp2[i-1],(dp1[n]-dp1[i-1])));
	}
	cout << ans;
 	return;
}

int main() {
   
   ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
   //freopen("input.txt", "r", stdin);
   //freopen("output.txt", "w", stdout);
    ll T;
    T=1;
    //cin >> T;
    //scanf("%lld",&T);
    ll CT = 0;
    
    //work();
    while(T--){
    	//cout << "Case #" << ++CT <<": " ;
    	//printf("Case %lld: ",++CT);
		solve();
	}
	
    return 0;
}
/*


*/

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

long long int knapsack1(vector<long long int> &wt,vector<long long int> &val,long long int n,long long int w, vector<vector<long long int>> &dp){
	
	// int n = wt.size();
	
	if(n==0||w==0){
		return 0;
	}
	
	if(dp[n][w]!=-1){
		return dp[n][w];
	}
	else{
		
		if(wt[n-1]<=w){
			dp[n][w] = max( val[n-1] + knapsack1(wt,val,n-1,w-wt[n-1],dp) , knapsack1(wt,val,n-1,w,dp) );
			return dp[n][w];
		}
		else{
			dp[n][w] = knapsack1(wt,val,n-1,w,dp);
			return dp[n][w];
		}
	}
	
}


int main(){
  
	long long int n,w,x,i,j;
	cin>>n>>w;
	// cout<<"n "<<n<<" w "<<w<<endl;
	vector<long long int> wt,val;
	
	for( i=1;i<=n;i++){
		for( j=1;j<=2;j++){
			if(j==1){
				cin>>x;
				wt.push_back(x);
				
			}
			if(j==2){
				cin>>x;
				val.push_back(x);
			}
		}
	}
	
	vector<vector<long long int> > dp( n+1 , vector<long long int> (w+1,-1));  

	// cout<<"weight"<<" ";
	// for(auto i = wt.begin();i!=wt.end();i++){
	// 	cout<<"YES "<<*i<<" "<<endl;
	// }
	// cout<<endl<<"val ";
	// for(auto i = val.begin();i!=val.end();i++){
	// 	cout<<"YES "<<*i<<" "<<endl;
	// }
	// cout<<endl;
	
	// // memset(dp,-1,sizeof(dp));
	
	cout<<knapsack1(wt,val,n,w,dp);

}

Measured memory_bytes: 83188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

int A, B;

void input() {
    cin >> A >> B;
}

void solve() {
    input();
    cout << max(0, A - 2 * B) << endl;
    return;
}

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

Measured memory_bytes: 256
object Main {
  
  def main(args: Array[String]) {
     val list = readLine().split(" ").map(_.toInt)
     val (a, b, c) = (list(0), list(1), list(2)) 
     var count = 0
     for (i <- a to b) {
       if (c % i == 0) count += 1   
     }
     println(count)
  }
}



Measured memory_bytes: 43808
import java.util.*;
public class Main {
 public static void main(String...args) {
   final Scanner sc = new Scanner(System.in);
   final int N = sc.nextInt();
   final char[] s = sc.next().toCharArray();
   int cnt = 0;
   for(int i = 0; i < N; i++)
     if(s[i] == 'R') cnt++;
   System.out.println(cnt * 2 > N ? "Yes" : "No");
 }
}

Measured memory_bytes: 22608
#include<cstdio>
using namespace std;
int insertionSort(int A[],int N){
    int v,j;
    for(int i=1;i<=N-1;i++){
        v=A[i];
        j=i-1;
        while(j>=0&&A[j]>v){
            A[j+1]=A[j];
            j--;
            A[j+1]=v;
        }
        for(int i=0;i<N;i++){
            if(i != (N-1)){
                printf("%d ",A[i]);
            }else{
                printf("%d\n",A[i]);
            }
        }
    }
    return 0;

}
int main(){
    int num;
    scanf("%d",&num);
    int A[num];
    for(int i=0;i<num;i++){
        scanf(" %d",&A[i]);
    }
    for(int i=0;i<num;i++){
            if(i != (num-1)){
                printf("%d ",A[i]);
            }else{
                printf("%d\n",A[i]);
            }
        }
    insertionSort(A,num);
    return 0;
}


Measured memory_bytes: 2712
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> cnt(N);
	vector<vector<int>> G(N);
	for (int i = 0; i < N-1; ++ i) {
		int u, v;
		cin >> u >> v;
		-- u; -- v;
		G[u].push_back(v);
		G[v].push_back(u);
		++ cnt[u];
		++ cnt[v];
	}
	vector<int> C(N);
	vector<int> a(N, -1);
	for (auto& x : C) cin >> x;
	sort(C.begin(), C.end());
	long long res = 0;
	for (int i = 0; i < N; ++ i) {
		int m = 1<<30, sel = 0;
		for (int j = 0; j < N; ++ j) {
			if (a[j] == -1 && cnt[j] < m) {
				m = cnt[j];
				sel = j;
			}
		}
		a[sel] = C[i];
		res += C[i] * cnt[sel];
		for (auto j : G[sel]) if (a[j] == -1) -- cnt[j];
	}
	cout << res << endl;
	for (int i = 0; i < N; ++ i) {
		if (i) cout << " ";
		cout << a[i];
	}
	cout << endl;
}


Measured memory_bytes: 1024
from bisect import bisect_left
n = int(input())
lis = [0]*13
for i in range(1,13):
   lis[i] = 26**i + lis[i-1]
#print(lis)
num = bisect_left(lis,n)
n -= lis[num-1]
n -= 1
ans = ''
for i in range(num):
   i = num-i-1
   ans += chr(n//(26**i) +97)
   n %= 26**i
print(ans)

Measured memory_bytes: 9212
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int ans=0;
while (1){
if ((x&1)||(y&1)||(z&1)) return printf("%d\n",ans),0;
ans++;
int a=x,b=y,c=z;
x=(b+c)/2;y=(c+a)/2;z=(a+b)/2;
if (x==a&&y==b&&z==c) return puts("-1"),0;
}
return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m, f, r;

    for (int i = 0;; i++) {
      m = sc.nextInt();
      f = sc.nextInt();
      r = sc.nextInt();
      if (m == -1 && f == -1 && r == -1) {// 入力の終了
        break;
      } else if (m == -1 || f == -1) {// 中間、期末いずれかを欠席F
        System.out.printf("F\n");
      } else if (m + f >= 80){// 合計80以上A
        System.out.printf("A\n");
      } else if (m + f >= 65){// 合計65以上B
        System.out.printf("B\n");
      } else if (m + f >= 50 || (m + f >= 30 && r >=50)){// 合計50以上、または30以上追試50以上C
        System.out.printf("C\n");
      } else if (m + f >= 30){// 合計30以上D
        System.out.printf("D\n");
      } else {// それ以外F
        System.out.printf("F\n");
      }
    }

    sc.close();
  }
}



Measured memory_bytes: 26320
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <limits>
#include <map>
#include <set>
#include <iomanip>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef std::numeric_limits<double> dbl;
const long long int LL_INF=1LL<<60;

vector<string> split(const string& input, char delimiter)
{
    stringstream stream(input);
    
    string field;
    vector<string> result;
    while (getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}

//#define DEBUG

ll A, B, C, D, E, M, N, K, Q, W, H, T, X, Y;

int main()
{
    cin >> N >> K;
    vector<ll> times(N);
    for (auto& t : times)
        cin >> t;

    sort(times.rbegin(), times.rend());
    int ans = 0;
    for (int i = 0; i < K; ++i)
        ans += times[i];
    cout << ans << endl;
    
    return 0;
}

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

using namespace std;

bool isKaibun(string s)
{
	for (int i = 0; i < (s.length()) / 2; i++) {
		if (s[i] != s[s.length() - 1 - i])
			return false;
	}

	return true;
}

int main()
{
	string s;
	cin >> s;
	string s1 = s.substr(0, (s.length() - 1) / 2);
	string s2 = s.substr((s.length() + 3) / 2 - 1);

	if (isKaibun(s) && isKaibun(s1) && isKaibun(s2))
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
A = input()
B = input()
C = input()

ai = bi = ci = 0
turn = 'a'
while 1:
    if turn == 'a':
        if ai >= len(A):
            print('A')
            exit()
        turn = A[ai]
        ai += 1
    elif turn == 'b':
        if bi >= len(B):
            print('B')
            exit()
        turn = B[bi]
        bi += 1
    else:
        if ci >= len(C):
            print('C')
            exit()
        turn = C[ci]
        ci += 1

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int a, b, c;
  cin >> a >> b >> c;

  int s;
  s = a + b + c;

  if (s <= 21) {
    cout << "win" << endl;
  } else {
    cout << "bust" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  long long int cnt[5]={0,0,0,0,0};
  string s;
  for(int i=0; i<n; i++){
    cin >> s;
    if(s[0] == 'M')cnt[0]++;
    if(s[0] == 'A')cnt[1]++;
    if(s[0] == 'R')cnt[2]++;
    if(s[0] == 'C')cnt[3]++;
    if(s[0] == 'H')cnt[4]++;
  }
  //for(int i=0; i<5; i++){
    //cout << cnt[i] << " ";
  //}
  //cout << endl;
  long long int ans=0;
  for(int i=0; i<5; i++){
    for(int j=i+1; j<5; j++){
      for(int k=j+1; k<5; k++){
        ans += cnt[i]*cnt[j]*cnt[k];
      }
    }
  }
  cout << ans << endl;
}
  

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

int main(){
  int N,K;
  cin>>N>>K;
  float p[N];
  float temp=0;
  for (int i=0;i<N;i++){
    cin>>temp;
    p[i]=(temp+1)/2;
  }
  double ans=0;
  double tempans=0;

  for (int i=0;i<K;i++){
    tempans=tempans+p[i];
  }
     ans=max(ans,tempans); 
  for (int i=0;i<N-K;i++){
    tempans=tempans-p[i]+p[i+K];
    ans=max(ans,tempans);
  }
  
 cout<<setprecision(15)<<ans<<endl;
  return 0;
}





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

const long long infinity = 1e18;




// vector<vector<long long> > dp( 100 , vector<long long> (1000000, 0));
int main(){
	int n,W;
	cin>>n>>W;
	
	int w[n];
    int v[n];
	int sum = 0;
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
		sum += v[i];
	}
    vector<vector<long long> > dp( n , vector<long long> (sum+1));
	for(int i=0;i<n;i++){
		for(int j=0;j<=sum;j++){
			dp[i][j] = infinity;
		}
	}

	dp[0][0] = 0;
	dp[0][v[0]] = w[0];
	
	for(int id=1;id<n;id++){
		dp[id][0] = 0;
		for(int j=1;j<=sum;j++){
			
			// Discard current object
			dp[id][j] = dp[id-1][j];
			
			// Pick current object
			if(j >= v[id])
				dp[id][j] = min(dp[id][j], w[id] + dp[id-1][j-v[id]]);
			
		}
	}
	
	long long answer;
	
	for(int val = sum;val>=0;val--){
		if(dp[n-1][val] <= W){
			answer = val;
			break;
		}
	}
	
	cout<<answer;
	
	return 0;
}


Measured memory_bytes: 82292
n = int(input())

# c_hash = {}
c_list = []
# n = 3
for i in range(n):
    s = input()
    c_list.append(''.join(sorted(s)))

# print(sorted(c_list))

c_hash = {}
for c in c_list:
    if c not in c_hash:
        c_hash[c] = 0
    c_hash[c] += 1
count = 0    
for k, v in c_hash.items():
    if v >= 2:

        
        # temp = factorial(v) / factorial(2) / factorial(v - 2)
        # temp = len(list(combinations(range(v),2)))
        temp = v * (v-1)/ 2
        count += temp

print(int(count))        

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

using namespace std;

static const ll INF = 1e15;

template<typename T>
static inline void chmin(T& ref, const T  value) {
    if (ref > value) ref = value;
}

template<typename T>
static inline void chmax(T& ref, const T value) {
    if (ref < value) ref = value;
}

struct Compressed {
    map<ll, ll> zip;
    vector<ll> unzip;

    int compress(vector<ll>& x) {
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());
        unzip.resize(x.size());
        for (int i = 0; i < x.size(); i++) {
            zip[x[i]] = i;
            unzip[i] = x[i];
        }
        return x.size();
    }
};

int main() {
    int n;
    cin >> n;
    vector<t4> rs(n);
    vector<ll> xs, ys;
    rep(i, n) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        rs[i] = tie(x1, y1, x2, y2);
        xs.push_back(x1);
        ys.push_back(y1);
        xs.push_back(x2);
        ys.push_back(y2);
    }
    Compressed xc, yc;
    xc.compress(xs);
    yc.compress(ys);
    vector<vector<int>> imos(yc.unzip.size(), vector<int>(xc.unzip.size(), 0));
    rep(i, n) {
        ll x1, y1, x2, y2;
        tie(x1, y1, x2, y2) = rs[i];
        imos[yc.zip[y1]][xc.zip[x1]]++;
        imos[yc.zip[y1]][xc.zip[x2]]--;
        imos[yc.zip[y2]][xc.zip[x1]]--;
        imos[yc.zip[y2]][xc.zip[x2]]++;
    }
    vector<vector<int>> sum(yc.unzip.size(), vector<int>(xc.unzip.size(), 0));
    for (int y = 0; y < yc.unzip.size(); y++) {
        for (int x = 0; x < xc.unzip.size(); x++) {
            if (x == 0) {
                sum[y][x] = imos[y][x];
            }
            else {
                sum[y][x] = sum[y][x - 1] + imos[y][x];
            }
        }
    }
    for (int y = 0; y < yc.unzip.size(); y++) {
        for (int x = 0; x < xc.unzip.size(); x++) {
            if (y < yc.unzip.size() - 1) {
                sum[y + 1][x] += sum[y][x];
            }
        }
    }
    ll area = 0;
    for (int y = 0; y < yc.unzip.size(); y++) {
        for (int x = 0; x < xc.unzip.size(); x++) {
            if (sum[y][x] != 0) {
                ll dy = yc.unzip[y + 1] - yc.unzip[y];
                ll dx = xc.unzip[x + 1] - xc.unzip[x];
                area += dy * dx;
            }
        }
    }
    cout << area << endl;
    return 0;
}



Measured memory_bytes: 128820
#include<stdio.h>
int main(void){
    unsigned long long h,sum=0,x=0;
    scanf("%llu",&h);

    for(x=1;h!=0;){
        h/=2;
        sum+=x;
        x*=2;
    }
    
    printf("%llu\n",sum);

    return 0;
}

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

#define all(v) v.begin(), v.end()
#define mp make_pair
#define EPS (int)1e-9
#define PI acos(-1)
#define endl '\n'
#define pb push_back
#define fi first
#define se second

using namespace std;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 1000000007;


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, x;
	cin >> n;

	int sz = 1e5;

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

	int ans = a[0] + a[1];
	ans = max (ans, a[sz] + a[sz-1]);

	for(int i = 1; i < sz; i++)
		ans = max(a[i-1] + a[i] + a[i+1], ans);

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

Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, a, n) for (int i = (a); i < (int)(n); i++)
#define repc(i, a, n) for (int i = (a); i <= (int)(n); i++)
#define all(t) t.begin(), t.end()
#define rall(t) t.rbegin(), t.rend()
#define mat(type, row, col, init)                                              \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
#define DBG(str) cerr << (str) << endl;
int main() {
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  vector<int> v(6), h(5);
  v[0] = ty - sy;
  v[1] = -v[0];
  v[2] = v[0] + 1;
  v[3] = -1;
  v[4] = -(v[0] + 1);
  v[5] = 1;
  rep(i, 0, v.size()) cerr << v[i] << endl;

  h[0] = tx - sx;
  h[1] = -(h[0] + 1);
  h[2] = h[0] + 1;
  h[3] = 1;
  h[4] = -(h[0] + 1);
  rep(i, 0, h.size()) cerr << h[i] << endl;
  int i, j, k;
  i = j = k = 0;

  while (1) {
    if (k % 2 == 0) {
      rep(l, 0, abs(v[j])) { cout << (v[j] < 0 ? "D" : "U"); }
      j++;
    } else {
      rep(l, 0, abs(h[i])) {
        cout<<(h[i]<0?"L":"R");
      }
      i++;
    }
    k++;
    if (k == 11) break;
  }

  return 0;
}


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

    int ans;

int main(void){
    int n;
    
    cin >> n;
    
    int p[n];
    
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    
    for(int i = 0; i < n-2; i++){
        if(( p[i] < p[i+1] && p[i+1] < p[i+2] ) || ( p[i] > p[i+1] && p[i+1] > p[i+2] )){
            ans++;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Relation{
public:
	Relation(int tmp_n,int tmp_m){
		n = tmp_n;
		m = tmp_m;
		V = new vector<int>[n];
		num_of_each = new int[n];
		group = new int[n];
		for(int i=0;i<n;i++){
			num_of_each[i] = 0;
			group[i] = 0;
		}
		group_number = 1;
	}

	void push(int s,int t){
		V[s].push_back(t);
		V[t].push_back(s);
		num_of_each[s]++;
		num_of_each[t]++;
	}

	void makeGroup(){
		int node,i;
		queue<int> Q;
		Q.push(0);
		group[0] = 1;
		while(true){
			while(!Q.empty()){
				node = Q.front();
				Q.pop();
				if(num_of_each[node] > 0){
					for(int k=0; k < num_of_each[node];k++){
						if(group[V[node][k]] == 0){
							group[V[node][k]] = group[node];
							Q.push(V[node][k]);
						}
					}
				}
			}
			group_number++;
			for(i=0;i<n;i++){
				if(group[i] == 0){
					group[i] = group_number;
					Q.push(i);
					break;
				}
			}
			if(i == n) break;
		}
	}

	bool canAccsess(int s,int t){
		return group[s] == group[t];
	}

private:
	vector<int>* V;
	int* num_of_each;
	int* group;
	int group_number;
	int n,m;
};

int main(){
	int n,m,s,t,q;
	scanf("%d %d",&n,&m);

	Relation relation(n,m);
	for(int i=0;i<m;i++){
		scanf("%d %d",&s,&t);
		relation.push(s,t);
	}
	relation.makeGroup();
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		scanf("%d %d",&s,&t);
		if(relation.canAccsess(s,t)){
			printf("yes\n");
		}else{
			printf("no\n");
		}
	}
    return 0;
}

Measured memory_bytes: 8836
#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<string> R;

const vector<int> dx = { 0, 1, 0, -1 };
const vector<int> dy = { -1, 0, 1, 0 };

int rec(int x, int y)
{
	R[y][x] = '0';

	for (int dir = 0; dir < 4; dir++)
	{
		if (0 <= x + dx[dir] && x + dx[dir] < 12 && 0 <= y + dy[dir] && y + dy[dir] < 12)
		{
			if (R[y + dy[dir]][x + dx[dir]] == '1')
			{
				rec(x + dx[dir], y + dy[dir]);
			}
		}
	}
}

int solve()
{
	int ret = 0;

	for (int i = 0; i < 12; i++)
	{
		for (int j = 0; j < 12; j++)
		{
			if (R[i][j] == '1')
			{
				rec(j, i); ret++;
			}
		}
	}

	return ret;
}

int main()
{
	while (true)
	{
		R = vector<string>(12);

		for (int i = 0; i < 12; i++)
		{
			if (!(cin >> R[i]))
			{
				return 0;
			}
		}

		cout << solve() << endl;
	}
}

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

constexpr int MAXN = 3e3 + 3;
constexpr int M = 998244353;

using namespace std;
using LL = long long;

LL dp[MAXN][MAXN], sum[MAXN][MAXN];
int n, S, a[MAXN];

int main() {
    std::ios::sync_with_stdio(false);
    cin >> n >> S;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        (dp[i][a[i]] += i) %= M;
        for (int s = a[i] + 1; s <= S; s++) {
            (dp[i][s] += sum[i - 1][s - a[i]]) %= M;
        }
        for (int s = 0; s <= S; s++) {
            (sum[i][s] = sum[i - 1][s] + dp[i][s]) %= M;
        }
    }
    LL res = 0;
    for (int i = 1; i <= n; i++)
        (res += dp[i][S] * (n - i + 1) % M) %= M;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 141056
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <random>
#include <math.h>
#include <algorithm>
#include <queue>
#define LL long long

using namespace std;

const int mod = 1e9+7;
const int maxn = 11234567;

bool isprim[1123456];
int p[1123456];
int tp;

int main()
{
    ios::sync_with_stdio(false);

    int t;
    int n, k, m;

    LL a, b;

    scanf("%lld%lld", &a, &b);

    if (a < b) swap(a, b);

    int ans = 1;
    memset(isprim, 0, sizeof(isprim));
    isprim[1] = 1;
    tp = 0;

    for (LL x = 2; x*x <= a; ++x)
    {
        bool f = 0;
        while (a%x == 0 && b%x == 0)
        {
            a /= x;
            b /= x;
            f = 1;
        }
        while (a%x == 0) a/=x;
        while (b%x == 0) b/=x;
        if (!isprim[x]) {
            p[tp++] = x;
            if (f)
                ans++;
        }
        for (LL i = 0; i < tp && p[i]*x*p[i]*x <= a; ++i)
        {
            isprim[p[i]*x] = 1;
        }
    }

    if (a%b == 0 && b != 1) ans++;

    printf("%d\n", ans);

    return 0;
}


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

int main() {
  string s;
  cin >> s;
  int x = s.size();
  int a = 0, b = 0;
  for (int i = 0; i < x; i++) {
    if (s[i] == '0') {
      a++;
    }
    else {
      b++;
    }
  }
  int ans = 0;
  if (a >= b) {
    ans = x - a + b;
  }
  else {
    ans = x + a - b;
  }
  cout << ans << endl;
}

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

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

int main(){
	long long a,b,c,d;	cin>>a>>b>>c>>d;
	--a;

	long long x=c*d/gcd(c,d);

	// cとdの最小公倍数は？


	long long bAns = b- (b/c + b/d -b/x);
	long long aAns = a- (a/c + a/d - a/x);

	cout<<bAns-aAns<<endl;

	return 0;
}


Measured memory_bytes: 256
s=int(input())
n1=s//100
n2=s%100
if n1>12 or n1==0:
    if n2>12 or n2==0:print("NA")
    else:print("YYMM")
else:
    if n2>12 or n2==0:print("MMYY")
    else:print("AMBIGUOUS")


Measured memory_bytes: 2940
#include<stdio.h>

typedef struct{
    int x;
    int y;
} point;

point num2point[100000];
int point2num[400][400];
int cost[100000];

int h, w, d;
int q;
int l, r;

void init();
void test();
void calc();
int diff_abs(int a, int b);

int main()
{
    int i;

    init();

    for (i = 0; i < q; i++) {
        scanf("%d %d\n", &l, &r);
        printf("%d\n", cost[r]-cost[l]);
    }

    return 0;
}

void init()
{
    int i, j;
    scanf("%d %d %d\n", &h, &w, &d);

    for(i = 0; i < h; i++) for(j = 0; j < w; j++){
        scanf("%d", &point2num[i][j]);
        num2point[point2num[i][j]].x = i;
        num2point[point2num[i][j]].y = j;
    }

    scanf("%d\n", &q);

    calc();
}

void calc()
{
    int i;
    int x1, x2;
    int y1, y2;

    for (i = 1; i <= d; i++)
        cost[i] = 0;

    for (i = d+1; i <= h*w; i++){
        x1 = num2point[i].x;
        x2 = num2point[i-d].x;
        y1 = num2point[i].y;
        y2 = num2point[i-d].y;
        cost[i] = cost[i-d] 
            + diff_abs(x1, x2) + diff_abs(y1, y2);
    }
}

int diff_abs(int a, int b)
{
    return a > b ? a - b : b - a;
}


Measured memory_bytes: 2560
i=require('fs').readFileSync('/dev/stdin','utf8');
i.includes('753')&&console.log(0);
if(!i.includes('753')){m=Infinity;i.split('').map((x,y)=>{if(y<i.length-2){s=i.substr(y,3);Math.abs(753-s)<m&&(m=Math.abs(753-s));}});console.log(m)}

Measured memory_bytes: 21192
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

int main()
{
    int64_t N;
    std::cin >> N;

    std::string SS;
    std::cin >> SS;

    std::map<std::string, int> A;

    A[SS] = 1;

    char prev = SS[SS.size()-1];

    for (int64_t i = 0; i < N-1; ++i) {
        std::string S;
        std::cin >> S;
        if (A.count(S) != 0) {
            std::cout << "No" << std::endl;
            return 0;
        }
        A[S] = 1;

        if (S[0] != prev) {
            std::cout << "No" << std::endl;
            return 0;
        }
        prev = S[S.size()-1];
    }
    std::cout << "Yes" << std::endl;

    return 0;
}


Measured memory_bytes: 256
def solve array
  count = 0

  (array.size - 1).step(1, -1) do |i|
    i.times do |j|
      if array[j] > array[j + 1]
        tmp = array[j + 1]
        array[j + 1] = array[j]
        array[j] = tmp
        count += 1
      end
    end
  end
  count
end

while (n = $stdin.gets.to_i) != 0 do
  array = Array.new
  n.times do
    array << $stdin.gets.to_i
  end
  p solve(array)
end

Measured memory_bytes: 6092
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;


void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int r;
    cin >> r;
    cout << r*r;

    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h> 
using namespace std;
using ll=long long;
const int mod=1e9+7;
struct node{
	ll a[50][50];
};
int n;
node mul(node x,node y){
	node ret;
	memset(ret.a,0,sizeof(ret.a));
	for(int i=0;i<n;++i){
		for(int k=0;k<n;++k){
			for(int j=0;j<n;++j){
				ret.a[i][j]=(ret.a[i][j]+x.a[i][k]*y.a[k][j]+mod)%mod;
			}
		}
	}
	return ret;
} 
ll calc(ll a,node res){
	node ans;
	for(int i=0;i<n;++i){
		ans.a[i][i]=1;
	}
	while(a>0){
		if(a&1){
			ans=mul(ans,res);
		}
		a>>=1;
		res=mul(res,res);
	}
	ll ret=0;
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			ret+=ans.a[i][j];
			if(ret>=mod){
				ret-=mod;
			} 
		}
	}
	return ret;
}
int main(){
	node res;
	ll k;
	cin>>n>>k;
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			cin>>res.a[i][j];
		}
	}
	cout<<calc(k,res)<<'\n';
	return 0;
}

Measured memory_bytes: 384
N = int(input())
A = list(map(int,input().split()))
B = [0]*N

for k in range(N,0,-1):
    t = 0
    l = 1
    while l*k-1 < N:
        t += B[l*k-1]
        l += 1
    if t%2 != A[k-1]%2:
        B[k-1] = 1

print(sum(B))
C = []
for k in range(N):
    if B[k] == 1:
        C.append(k+1)
print(*C)


Measured memory_bytes: 70236
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define fast ios::sync_with_stdio(false); cin.tie(NULL);
const double eps = 1e-6;

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

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

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

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

#define int long long
const int N  = 2e5 + 5;
const int mod = 1e9 + 7;
int fact[N];

void start(){

	fact[0] = 1;

	for(int i = 1 ; i < N ; ++i)
		fact[i] = fact[i-1]*i%mod;
}

int power(int a , int n){

	int res = 1;
	while(n){

		if(n&1)
			res*=a , res%=mod;
		a*=a;
		a%=mod;
		n/=2;
	}
	return res;
}

int invMod(int x){

	return power(x , mod-2);
}

void solve(){

	start();

	int n , a , b;
	cin>>n>>a>>b;

	int ans = power(2 , n);

	--ans;
	ans+=mod;
	ans%=mod;

	int x = 1;
	for(int i = n - a + 1 ; i <= n ; ++i)
		x*=i , x%=mod;
	x*=invMod(fact[a]);
	x%=mod;
	ans-=x;
	ans+=mod;
	ans%=mod;
	x = 1;

	for(int i = n-b + 1 ; i <= n ; ++i)
		x*=i , x%=mod;
	x*=invMod(fact[b]);
	x%=mod;
	ans-=x;
	ans+=mod;
	ans%=mod;

	cout<<ans<<endl;

}

signed main(){

    fast;
    int t = 1;
    //cin>>t;
    for(int i = 1 ; i <= t; ++i){

    	solve();
    }
}


Measured memory_bytes: 1792
#include <stdio.h>

int Dice[6]={1,6,2,5,3,4};
char str[6][10]={"North","East","West","South","Right","Left"};

void init(){
	Dice[0]=1;
	Dice[1]=6;
	Dice[2]=2;
	Dice[3]=5;
	Dice[4]=3;
	Dice[5]=4;
}

long int solve(int p){
	int temp;
	if(p==0){
		temp=Dice[3];
		Dice[3]=Dice[0];
		Dice[0]=Dice[2];
		Dice[2]=Dice[1];
		Dice[1]=temp;
	}
	else if(p==1){
		temp=Dice[0];
		Dice[0]=Dice[5];
		Dice[5]=Dice[1];
		Dice[1]=Dice[4];
		Dice[4]=temp;
	}
	else if(p==2){
		temp=Dice[0];
		Dice[0]=Dice[4];
		Dice[4]=Dice[1];
		Dice[1]=Dice[5];
		Dice[5]=temp;
	}
	else if(p==3){
		temp=Dice[3];
		Dice[3]=Dice[1];
		Dice[1]=Dice[2];
		Dice[2]=Dice[0];
		Dice[0]=temp;
	}

	else if(p==4){
		temp=Dice[2];
		Dice[2]=Dice[4];
		Dice[4]=Dice[3];
		Dice[3]=Dice[5];
		Dice[5]=temp;
	}
	else{
		temp=Dice[2];
		Dice[2]=Dice[5];
		Dice[5]=Dice[3];
		Dice[3]=Dice[4];
		Dice[4]=temp;
	}
	
	//printf("p=%d a=%d\n",p,Dice[0]);
	
	return Dice[0];

	
}

int main(void)
{
	int n,i,j;
	long int sum;
	char s[10];
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		init();
		sum=1;
		for(i=0;i<n;i++){
			scanf("%s",s);
			for(j=0;j<6;j++){
				if(strcmp(str[j],s)==0){
					sum+=solve(j);
					break;
				}
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}

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

using namespace std;


void solve(){
    int a, b;
    cin>>a>>b;
    cout<<a*b<<"\n";
}


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

    //int T; cin>>T; while(T--)
        solve();
}

Measured memory_bytes: 3640
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void)
{
    int i=0,j=0,a=1000,b,c;
    char s[1010];
    scanf("%s",s);
    b=strlen(s);
    if(s[b-1]=='s'){
        s[b+2]=s[b];
        s[b]='e';
        s[b+1]='s';
    }
    else{
        s[b+1]=s[b];
        s[b]='s';
    }
    printf("%s",s);

    return 0;
}

Measured memory_bytes: 1712
n = int(input())
p = []
for i in range(n):
    a,b = map(int,input().split())
    p.append([b,a])
p.sort()
q = 1
s = 0
for i in range(n):
    s += p[i][1]
    if p[i][0] >= s:
        continue
    else:
        q = 0
        print('No')
        break
if q == 1:
    print('Yes')

Measured memory_bytes: 35608
mod=10**9+7    
n,k=map(int,input().split())
cnt=[0]*(k+1)
for i in range(k,0,-1):
    cnt[i]+=pow(k//i,n,mod)
    for j in range(2,k//i+1):
      cnt[i]-=cnt[i*j]
ans=0
for i in range(1,k+1):
    ans+=i*(cnt[i])%mod
    ans%=mod
print(ans)

Measured memory_bytes: 69100
#include <stdio.h>
int a[9][9];
void check(int x,int y){
    for(int i=0;i<9;i++){
        if(a[i][y]==a[x][y]&&i!=x){
            printf("*%d",a[x][y]);
            return;
        }
    }
    for(int i=0;i<9;i++){
        if(a[x][i]==a[x][y]&&i!=y){
            printf("*%d",a[x][y]);
            return;
        }
    }
    for(int i=x-x%3;i<x-x%3+3;i++){
        for(int j=y-y%3;j<y-y%3+3;j++){
            if(a[i][j]==a[x][y]&&(i!=x||j!=y)){
                printf("*%d",a[x][y]);
                return;
            }
        }
    }
    printf(" %d",a[x][y]);
    return;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        if(i>0)printf("\n");
        for(int j=0;j<9;j++){
            for(int k=0;k<9;k++){
                scanf("%d",&a[j][k]);
            }
        }
        for(int j=0;j<9;j++){
            for(int k=0;k<9;k++){
                check(j,k);
            }
            printf("\n");
        }
    }
}

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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	ll n, a, b;
	ll ans = 0;

	cin >> n >> a >> b;

	FOR(i, 1, n + 1) {
		ll sum;
		if (i != 10000) {
			ll a = i / 1000;
			ll b = (i % 1000) / 100;
			ll c = (i % 1000 % 100) / 10;
			ll d = i % 1000 % 100 % 10;
			sum = a + b + c + d;
		}
		else {
			sum = 1;
		}

		if (sum >= a && sum <= b) {
			ans += i;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <set>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

#define ll long long
const ll N = 1000000000000000;

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

    set<string> ss;
    for (int i = 0; i<n;++i) {
        string s; cin >>s;
        ss.insert(s);
    }

    cout << ss.size();

    return 0;
}

Measured memory_bytes: 19100
S = input()
ans = {0:1}
memo = [0]
last = 1
for ind, s in enumerate(S[::-1]):
    memo.append((int(s) * last + memo[-1]) % 2019)
    last *= 10
    last %= 2019
    if(memo[-1] in ans):
        ans[memo[-1]] += 1
    else:
        ans[memo[-1]] = 1

res = 0
for key in ans.keys():
    res += ans[key]*(ans[key]-1)//2
print(res)

Measured memory_bytes: 16600
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
void init_fact(){
    kaijo[0]=1;
    for(int i=1;i<=2000000;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=MOD;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%MOD;
    int memo=modpow(a,b/2);
    return memo*memo%MOD;
}
int comb(int a,int b){
    if(!kaijo[0])init_fact();
    return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int inv(int x){
    x=modpow(x,MOD-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
int n,p[8],q[8];
signed main(){
    cin>>n;
    rep(i,n)cin>>p[i];
    rep(i,n)cin>>q[i];
    vector<int>v;
    rep(i,n)v.pb(i+1);
    int jun=0,a,b;
    do{
        jun++;
        rep(i,n)if(v[i]!=p[i])goto notP;
        a=jun;
        notP:;
        rep(i,n)if(v[i]!=q[i])goto notQ;
        b=jun;
        notQ:;
    }while(next_permutation(all(v)));
    cout<<abs(a-b)<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

int main()
{
    int a,b,c,flag=0;
    cin>>a>>b>>c;
    if(a==b&&a!=c) flag=1;
    else if(a==c&&a!=b) flag=1;
    else if(b==c&&b!=a) flag=1;
    if(flag) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}


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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define what_is(x) cerr << #x << " is " << x << endl;
#define debug(v) for (auto el : v) { cerr << el << ' '; } cerr << endl;

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

const int N = 80;
const int MID = N*N*2;
int a[N][N], b[N][N], c[N][N];
int dp[N][N][N*N*4+1];

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	int h, w;
	scanf("%d%d", &h, &w);
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++) scanf("%d", &a[i][j]);
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++) scanf("%d", &b[i][j]);

	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++) c[i][j] = a[i][j] - b[i][j];
	dp[0][0][MID+c[0][0]] = dp[0][0][MID-c[0][0]] = 1;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			for (int v = 0; v <= 2*MID; v++) {
				if (!dp[i][j][v]) continue;
				if (i + 1 < h)
					dp[i+1][j][v+c[i+1][j]] = dp[i+1][j][v-c[i+1][j]] = 1;
				if (j + 1 < w)
					dp[i][j+1][v+c[i][j+1]] = dp[i][j+1][v-c[i][j+1]] = 1;
			}
		}
	}

	/*
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			printf("<%d,%d>:", i, j);
			for (int v = 0; v <= 2*MID; v++)
				if (dp[i][j][v]) printf(" %d", v);
			puts("");
		}
	}
	*/

	int best = 1e9;
	for (int v = 0; v <= 2*MID; v++) {
		if (dp[h-1][w-1][v]) best = min(best, abs(v - MID));
	}
	printf("%d\n", best);
}


Measured memory_bytes: 638464
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		int n = int.Parse(Console.ReadLine());//long.Parseはstringをlongに変換。
		long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
    long[,] dp = new long[n+1,n+1];//dp[左から取った数、右から取った数] := x-yの残り増加量

    for(int i = 0; i <= n; i++) dp[i,n-i] = 0;

    for(int i = n-1; i >= 0; i--)//既に取った数
    {
      for(int j = 0; j <= i; j++)//左から取った数
      {
        //Console.WriteLine(j+" "+(i-j));
        if(i % 2 == 0)//先手の番
        {
          dp[j,i-j] = Math.Max(dp[j,i-j+1]+nums[n-1-i+j], dp[j+1,i-j]+nums[j]);
        }else//後手の番
        {
          dp[j,i-j] = Math.Min(dp[j,i-j+1]-nums[n-1-i+j], dp[j+1,i-j]-nums[j]);
        }
        //Console.WriteLine(j+" "+(i-j)+" "+dp[j,i-j]);
      }
    }
    
		Console.WriteLine(dp[0,0]);
	}
}

Measured memory_bytes: 83552