akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb(x) emplace_back(x)
#define forn(i,N) for(int i=0;i<N;i++)
#define rep(i,x,N) for(int i=x;i<=N;i++)
#define revrep(i,x,N) for(int i=x;i>=N;i--)
#define ar array

using namespace std;
using ll=long long int;
using ld=long double;
using vi=vector<int>;
using vll=vector<ll>;
using vd=vector<double>;
using vvi=vector<vi>;
int ctoi(char c) {return c-'0';}
int slen(string s) {return s.length();}
int vsize(vi a) {return (int)a.size();}
int in() {int x;cin>>x;return x;}
void tf(bool ok) {cout<<(ok ? "YES" : "NO")<<endl;}

//https://dmoj.ca/problem/dpv

const int MAXN = 1e5 + 10;

vector<int> g[MAXN];
ll dp[MAXN],c[MAXN],ans[MAXN];
int N,M;

void dfs1(int e,int p){
	dp[e]=1;
	vi cdrn;
	for(int& u : g[e]){
    if(u!=p) {
      dfs1(u,e);
      dp[e]=(dp[e]*(dp[u]+1))%M;
      cdrn.pb(u);
    }
	}

	vll ps,ss;
	ll pref=1,suf=1;
	for(int i=0;i<(int)cdrn.size();i++){
		ps.pb(pref);
		pref=(pref*(dp[cdrn[i]]+1))%M;
	}
	for(int i=(int)cdrn.size()-1;i>=0;i--){
		ss.pb(suf);
		suf=(suf*(dp[cdrn[i]]+1))%M;
	}
	reverse(ss.begin(),ss.end());
	for(int i=0;i<(int)cdrn.size();i++){
		c[cdrn[i]]=(ps[i]*ss[i])%M;
	}
}

void dfs2(int e,int p){
	ans[e]=(dp[e]*c[e])%M;
	for(int& u: g[e]){
      if(u!=p) {
      c[u]=(c[u]*c[e]+1)%M;
      dfs2(u,e);
    }
	}
}

int main(){

cin>>N>>M;
for(int i=1;i<N;i++){
  int u,v;
  cin>>u>>v;
  g[u].pb(v);
  g[v].pb(u);
}

dfs1(1,-1);
c[1] = 1;
dfs2(1,-1);

for(int i=1;i<=N;i++)
  cout<<ans[i]<<endl;
return 0;
}

Measured memory_bytes: 25020
a=gets.to_i
c=[]
first = 0
sec = 0
a.times do
  b = gets.chomp.to_i
  c << b
  if a == 1
    first = b
  elsif b > first
    sec = first
    first = b
  elsif b > sec
    sec = b
  end
end
c.each{|t|
  if t != first
    puts first
  else
    puts sec
  end
}

Measured memory_bytes: 4732
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//while adding and subs check if mod becomes -ve
//while using an integer directly in a builtin function add ll

#include <bits/stdc++.h>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007 //998244353
#define lld long double
#define mii map<int, int>
#define mci map<char, int>
#define msi map<string, int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
typedef std::numeric_limits< double > dbl;
using namespace std;
const long long N=200005, INF=2000000000000000000;
int power(int a, int b, int p)
    {
        if(a==0)
        return 0;
        int res=1;
        a%=p;
        while(b>0)
        {
            if(b&1)
            res=(res*a)%p;
            b>>=1;
            a=(a*a)%p;
        }
        return res;
    }

int32_t main()
{
    IOS;
    string s;
    cin>>s;
    if(s[1]=='B')
    cout<<"ARC";
    else
    cout<<"ABC";
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n; scanf("%d", &n);
	
	if(n < 1200) printf("ABC\n");
	else if(n < 2800) printf("ARC\n");
	else printf("AGC\n");
	return 0;
}


Measured memory_bytes: 256
N = int(input())
char = "abcdefghij"
prev = ["a"]
results = []
for i in range(N-1):
  results = []
  for p in prev:
    for j in range(len(set(p))+1):
      results.append(p+char[j])
  prev = results
if N == 1:
  print("\n".join(prev))
else:
  print("\n".join(results))

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


vector<vector<int>>   switches;  // 電球が持つスイッチ
vector<int> p;   // 電球が点灯するスイッチの数が偶数なら0奇数なら1

int dfs(vector<int> &sv, int depth) {
  // ベースケース
  if (depth == sv.size()) {
    bool ok = true;
    rep(i, switches.size()) {
      int count = 0;
      rep(j, switches[i].size()) {
        if (sv.at(switches[i][j])) {
          count++;
        }
      }
      if (count % 2 != p[i]) {
        ok = false;
      }
    }

    if (ok) {
      return 1;
    } else {
      return 0;
    }
  }

  // 再帰ステップ
  int ans = 0;
  rep(i, 2) {
    sv[depth] = i;
    ans += dfs(sv, depth + 1);
  }

  return ans;
}

int main(void) {
  int N;    // 1~Nのスイッチ  
  int M;    // 1~Mの電球
  cin >> N >> M;

  switches = vector<vector<int>>(M);
  rep(i, M) {
    int k;
    cin >> k;
    switches.at(i).resize(k);
    rep(j, k) {
      cin >> switches.at(i).at(j);
      switches.at(i).at(j)--;   // 1~なのを0~にする
    }
  }

  p = vector<int>(M);
  rep(i, M) {
    cin >> p.at(i);
  }

  vector<int> sv(N, 0);  // スイッチの状態
  cout << dfs(sv, 0) << endl;
 
  return 0;
}

Measured memory_bytes: 256
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            final String s = reader.readLine();

            final String sl[] = s.split(" ");
            String A = sl[0];
            String B = sl[1];
            String C = sl[2];

            System.out.println(
                A.charAt(A.length() - 1) == B.charAt(0)
                && B.charAt(B.length() - 1) == C.charAt(0) ?
                "YES" : "NO");
        }
    }
}


Measured memory_bytes: 22612
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include<numeric>
#include<limits.h>
#include<utility>
#include<cstdlib>
#include<bitset>
#define LP(i,n) for(int i=0;i<n;i++)
#define LPIN(n,a) for(int i=0;i<n;i++)cin >> a[i]
using namespace std;

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int ans  = a  + b + c;
    cout << ans - max({a,b,c}) << endl;
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repl(i, l, r) for (int i = l; i < r; ++i)
#define rep(i, n) repl(i, 0, n)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using G = vector<vector<int>>;
const int MOD = 1000000007;
const int INF = 1001001001;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, -1, 0, 1};

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    rep(i, n) {
        cin >> a[i];
        sum += a[i];
    }
    ll ans = 0;
    rep(i, n) {
        sum -= a[i];
        ll k = sum % MOD;
        ans += a[i] * k;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}


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

int main(){
	int X,k,waru=1,sum=0;
  	cin>>X;
  	k=X;
  	
  	for(int j=0;k>10;j++){
  		for(int i=0;i<9-j;i++){
      	waru=waru*10;
    	}
      	sum += k/waru;
      	k = k%waru;
       
      	waru=1;
      	
 
    }
  	int FX = sum+k;
  
  	if(X%FX==0){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
}
      	
      	

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

using namespace std;

const int maxn = 1e6+7;
typedef long long ll;
const int mod = 998244353;
#define IO cin.tie(0,ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()

int s[]={0,2,5,5,4,5,6,3,7,6},a[maxn],ans[maxn],n,m,dp[maxn];
int cmp(int a,int b){
    if(s[a]!=s[b]) return s[a]<s[b];
    return a>b;
}
 
int cmp1(int a,int b){
    return a>b;
}
 
int main(){
 
    n=read,m=read;
    for(int i=0;i<m;i++){
        a[i]=read;
    }
    memset(dp,-1,sizeof(dp));
    dp[0]=1;
 
    int vis[10]={0};
    for(int i=0;i<m;i++){
        for(int j=s[a[i]];j<=n;j++){
            dp[j]=max(dp[j],dp[j-s[a[i]]]+1);
        }
    }
 
    sort(a,a+m,cmp1);
    while(n){
        for(int i=0;i<m;i++){
            if(n>=s[a[i]] && dp[n-s[a[i]]]+1==dp[n]){
                putchar(a[i]+'0');
                n=n-s[a[i]];break;
            }
        }
    }
 
    puts("");
    return 0;
}

Measured memory_bytes: 6400
#include<bits/stdc++.h>
#include<cstdio>
 
#define gc getchar
#define db double
#define ll long long int
#define ull unsigned long long int
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define sclu(x) scanf("%llu", &x)
#define scd(x) scanf("%lf", &x)
#define pass cout<<"pass\n"
#define vi vector<int>
#define pb push_back
#define vec vector
#define vi vector<int>
#define el "\n"
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define f(i,x,y) for(int i=x;i<y;++i)
#define ff(i,x,y) for(int i=x;i<=y;++i)
#define MOD 1000000007
#define MAX2 1000001
#define MAX 103
#define pbb pair<bool,bool>

using namespace std;

string a,b;
int len;

bool chk(int k) {
	string s = b;
	for(int j=0,i=k;i<k+len;++i,++j) {
		s[j] = b[i%len];
	}
	if(s == a) return true;
	return false;
}

int main() {
	cin >> a;
	cin >> b;
	if(a.length() != b.length()) {
		cout << "No\n"; return 0;
	}
	len = a.length();
	bool fl = false;
	for(int i=0;i<len;++i) {
		if(b[i]==a[0] && chk(i)) {
			fl = true;
			break;
		}
	}
	if(fl) cout << "Yes\n";
	else cout << "No\n";
	
	return 0;
}





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


int main()
{ 
 ll a,b,c,k;
 cin>>a>>b>>c>>k;
 ll ans=0;
 if(k<=a)
  cout<<k;
 else if(a+b>=k)
  cout<<a;
 else
  {
      if(k<a+b+c)
      {
         cout<<a-(k-a-b);
      }
      else{
          cout<<a-c;
      }
  }  
  
return 0;
}


Measured memory_bytes: 3632
package main

import (
  "bufio"
  "fmt"
  "os"
  "sort"
  "strconv"
  "strings"
)

const size = 1000000
var reader = bufio.NewReaderSize(os.Stdin,size)
func NextLine() string {
  var line,buffer []byte
  var isPrefix bool = true
  var err error
  for ;isPrefix; {
    line,isPrefix,err = reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
  }
  return string(buffer)
}
func NextInts() (int,int) {
  var n,k int
  var s []string = strings.Split(NextLine()," ")
  n,_ = strconv.Atoi(s[0])
  k,_ = strconv.Atoi(s[1])
  return n,k
}
func NextIntArray() []int {
  var s []string = strings.Split(NextLine()," ")
  var n int = len(s)
  var a []int = make([]int,n)
  for i:=0;i<n;i++ {
    a[i],_ = strconv.Atoi(s[i])
  }
  return a
}

func main() {
  var n,k int = NextInts()
  var a []int = NextIntArray()
  if n == 1 {
    if a[0] == k {
      fmt.Println("POSSIBLE")
    } else {
      fmt.Println("IMPOSSIBLE")
    }
    os.Exit(0)
  }
  sort.Ints(a)
  var g int = gcd(a[1],a[0])
  for i:=2;i<n;i++ {
    g = gcd(a[i],g)
  }
  if k%g == 0 && a[n-1] >= k {
    fmt.Println("POSSIBLE")
  } else {
    fmt.Println("IMPOSSIBLE")
  }
}
func gcd(x int,y int) int {
  if x%y == 0 { return y }
  return gcd(y,x%y)
}

Measured memory_bytes: 5888
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <numeric>
using namespace std;
#define MAX_N 100

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; }
const long long INF = 1LL << 60;

// Input
int K;
string S;

int main() {
  cin >> K;
  cin >> S;

  if ((int)(S.length()) > K) {
    cout << S.substr(0,K) << "..." << endl;
  } else {
    cout << S << endl;
  }
}


Measured memory_bytes: 3636
N, M = map(int, input().split())
H = list(map(int, input().split()))
l = [1]*N
for i in range(M):
  a, b = map(int, input().split())
  if H[a-1] < H[b-1]:
    l[a-1] = 0
  elif H[a-1] > H[b-1]:
    l[b-1] = 0
  else:
    l[a-1] = 0
    l[b-1] = 0
    
print(sum(l))

Measured memory_bytes: 20116
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int num, ball, a, b;
		int A[] = new int[10], B[] = new int[10];
		boolean answer[], done;
		Scanner scan = new Scanner(System.in);
		
		num = scan.nextInt();
		answer = new boolean[num];
		for(int i=0;i<num;i++){
			a=0; b=0;
			A[0]=scan.nextInt(); B[0]=0;
			done=false;
			for(int j=1;j<10;j++){
				ball = scan.nextInt();
				if(done) continue;
				if(ball<A[a] && ball<B[b]){
					answer[i] = false;
					done = true;
				}
				else if(ball>A[a] && ball<B[b]){
					a++;
					A[a]=ball;
				}
				else if(ball<A[a] && ball>B[b]){
					if(b==0)b--;
					b++;
					B[b]=ball;
				}
				else{
					if(ball-A[a]>ball-B[b]){
						b++;
						B[b]=ball;
					}
					else{
						a++;
						A[a]=ball;
					}
				}
			}
			if(!done)answer[i]=true;
		}
		
		for(int i=0;i<num;i++){
			if(answer[i]) System.out.println("YES");
			else System.out.println("NO");
		}
	}

}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define REPW(i,n) for(i=0;i<(int)(n);++i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------
const int MOD=1e9+7;

int cnt=0;
void merge_sort(vector<int> &a) {
    int n = a.size();
    if (n==1) return;

    vector<int> b(begin(a), begin(a) + n/2);
    vector<int> c(begin(a) + n/2, end(a));
    merge_sort(b);
    merge_sort(c);

    for (int i = 0, j = 0, k = 0; i < n; ++i) {
        if (k == c.size())      a[i] = b[j++];
        else if (j == b.size()) a[i] = c[k++];
        else if (b[j] < c[k])   a[i] = b[j++];
        else                    a[i] = c[k++];
        cnt++;
    }
}
signed main() {
    int n;
    cin>>n;
    vector<int> a(n);
    cin>>a;
    merge_sort(a);
    cout<<a<<endl;
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 14508
#include<bits/stdc++.h>
using namespace std;
int b[10001];
int main()
{
	int n,tot=1;
	cin>>n;
	while(!b[n])
	{b[n]=1;
	 if(n%2)n=3*n+1;
	 else
	  n/=2;
	 tot++;
	}
	cout<<tot<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (V)) cout <<x <<" " <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


int main() {
  int N,K; cin >>N >>K;
  vector<bool> trick(N, true);
  rep(q, K){
    int d; cin >>d;
    rep(qq, d){
      int a; cin >>a; a--;
      trick[a] = false;
    }
  }
  int res = 0;
  rep(i, N) if (trick[i]) res++;
  cout <<res <<endl;
}

Measured memory_bytes: 3632
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        long d = sc.nextLong();
        long max = Long.MIN_VALUE;
        max = Math.max(max, a*c);
        max = Math.max(max, a*d);
        max = Math.max(max, b*c);
        max = Math.max(max, b*d);
        System.out.println(max);
        sc.close();

    }

}


Measured memory_bytes: 35652
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <utility>

int memo[200004];
int main(){
  int N;
  scanf("%d", &N);
  std::vector<int > C(N);
  for (int i=0; i<N;i++){
    scanf("%d", &C[i]);
  }
  C.erase(unique(C.begin(), C.end()), C.end());
  std::vector<long long > dp(N+4);
  dp[0]=1;
  long long mod = 1e9+7;
  for (int i=0; i<200004;i++){
    memo[i]=-1;
  }
  for (int i=0; i<C.size(); i++){
    dp[i+1] = dp[i];
    if (memo[C[i]]!=-1){
      dp[i+1] += dp[memo[C[i]]];
      dp[i+1] %= mod;
    }
    memo[C[i]] = i+1;
    //printf("%d, dp=%d\n", C[i], dp[i+1]);
  }
  std::cout << dp[C.size()] << std::endl;
  return 0;
}

Measured memory_bytes: 3328
import math

EPS = 1e-10

def equals(a, b):
    return abs(a - b) < EPS


class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __add__(self, p):
        return Point(self.x + p.x, self.y + p.y)

    def __sub__(self, p):
        return Point(self.x - p.x, self.y - p.y)

    def __mul__(self, a):
        return Point(self.x * a, self.y * a)

    def __rmul__(self, a):
        return self * a

    def __truediv__(self, a):
        return Point(self.x / a, self.y / a)

    def norm(self):
        return self.x * self.x + self.y * self.y

    def abs(self):
        return math.sqrt(self.norm())

    def __lt__(self, p):
        if self.x != p.x:
            return self. x < p.x
        else:
            return self.y < p.y

    def __eq__(self, p):
        return equals(self.x, p.x) and equals(self.y, p.y)


class Segment:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2


def dot(a, b):
    return a.x * b.x + a.y * b.y


def cross(a, b):
    return a.x * b.y - a.y * b.x


def isOrthogonal(s1, s2):
    return equals(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0)


def isParallel(s1, s2):
    return equals(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0)


if __name__ == '__main__':
    q = int(input())
    ans = []
    for i in range(q):
        x0, y0, x1, y1, x2, y2, x3, y3 = [int(v) for v in input().split()]
        s1 = Segment(Point(x0, y0), Point(x1, y1))
        s2 = Segment(Point(x2, y2), Point(x3, y3))
        if isParallel(s1, s2):
            ans.append(2)
        elif isOrthogonal(s1, s2):
            ans.append(1)
        else:
            ans.append(0)

    for v in ans:
        print(v)


Measured memory_bytes: 5824
#include <bits/stdc++.h>
using namespace std;
vector<int> dish;
int temp;
int m = 10;
int ct = 0;
int main(){
    for(int i = 0; i < 5; ++i){
        cin >> temp;
        dish.push_back(temp);
    }
    
    for(int i = 0; i < 5; ++i){
        if(dish[i]%10 == 0){
            continue;
        }
        if(dish[i]%10 < m){
            m = dish[i]%10;
            ct = i;
        }
    }
    
    int sum = 0;
    for(int i = 0; i < 5; ++i){
        if(i == ct){
            sum += dish[i];
        }else if(dish[i]%10 == 0){
            sum += dish[i];
        }else{
            sum += dish[i] + (10 - dish[i]%10);
        }
    }
    
    cout << sum << endl;
    
}

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

using namespace std;

int n, a, b, c;
int d[105];

int main() {
    cin >> n >> a >> b >> c;

    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }

    sort(d, d + n, greater<int>());

    int sum = c;
    int maxV = 0;

    for (int k = 0; k < n; k++) {
        sum += d[k];
        maxV = max(maxV, sum / (a + b * (k + 1)));
    }

    cout << maxV << endl;
}

Measured memory_bytes: 3132
import sys
def gcd(a,b):
    if b== 0:return a
    return gcd(b,a%b)
def return_lcm(a,b):
    prime = gcd(a,b)
    return prime*(a/prime)*(b/prime)
def solve():
    a = []
    for line in sys.stdin:
        digit_list = line.split(' ')
        new_list = []
        for j in digit_list:
            new_list.append(int(j))
        a.append(new_list)
    for data in a:
        print str(gcd(data[0],data[1])) + ' ' + str(return_lcm(data[0],data[1]))

if __name__ == "__main__":
    solve()

Measured memory_bytes: 6344
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
typedef long long lint;
const int N=55;
int n,val[N],mx,mn;

namespace utils{
	template <class T> inline void apn(T &x,const T y){x=x<y?x:y;}
	template <class T> inline void apx(T &x,const T y){x=x>y?x:y;}
	inline int nxi(){
		int x=0;
		char c;
		while(((c=getchar())>'9'||c<'0')&&c!='-');
		const bool f=c=='-'&&(c=getchar());
		while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
		return f?-x:x;
	}
}
using namespace utils;

int main(){
	mn=mx=1;
	n=nxi();
	for(int i=1; i<=n; ++i){
		val[i]=nxi();
		if(val[mx]<val[i]) mx=i;
		if(val[mn]>val[i]) mn=i;
	}
	if(val[mx]>0&&val[mn]<0){
		printf("%d\n",n*2-2);
		if(val[mx]>-val[mn]){
			for(int i=1; i<=n; ++i){
				if(i!=mx) printf("%d %d\n",mx,i);
			}
		}
		else{
			for(int i=1; i<=n; ++i){
				if(i!=mn) printf("%d %d\n",mn,i);
			}
			val[mx]=-1;
		}
	}
	else printf("%d\n",n-1);
	if(val[mx]>0){
		for(int i=2; i<=n; ++i){
			printf("%d %d\n",i-1,i);
		}
	}
	else{
		for(int i=n-1; i; --i){
			printf("%d %d\n",i+1,i);
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
const int n = 100;
void insertionSort(int A[], int N);


int main(){
  int i, N;
  int A[n];
  scanf("%d", &N);
  for(i = 0; i < N; i++){
    scanf("%d", &A[i]);
  }

  insertionSort(A, N);

  return 0;
}

void insertionSort(int A[], int N){
  int i, j, k, v;
  
  for(k = 0; k < N; k++){
    printf("%d", A[k]);
    if(k == N-1){
      printf("\n");
    }else{
      printf(" ");
    }
  }
  
  for(i = 1; i < N; i++){
    j = i-1;
    v = A[i];

    while(j >= 0 && A[j] > v){
      A[j+1] = A[j];
      j--;
    }

    A[j+1] = v;
    for(k = 0; k < N; k++){
      printf("%d", A[k]);
      if(k == N-1){
        printf("\n");
      }else{
        printf(" ");
      }
    }

  }
}



Measured memory_bytes: 2076
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,x,y;
    cin>>n>>m;
    getchar();
    string xi;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
                cin>>xi;
                if(xi=="snuke"){
                        x=i,y=j;
                        break;
                }
        }
        getchar();
    }
    char ch='A'+y-1;
    cout<<ch<<x<<endl;
}


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

import bisect

dp = [-1]*(n+1)

for i in range(n):
  v = int(input())
  l = bisect.bisect_left(dp, v)
  if l==n+1:
    l -= 1
  if dp[l]<v:
    dp[l] = v
  else:
    dp[l-1] = v

cnt = 0
for i in range(n, 0, -1):
  if dp[i]>=0:
    cnt += 1
  else:
    break
    
print(cnt)

Measured memory_bytes: 46808
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 998244353;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

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


int main() {
	string S;
	cin >> S;
	ll N = S.size();

	ll c[3] = {};
	rep(i, N) c[S[i] - 'a']++;
	sort(c, c + 3);

	string ans = "YES";
	rep(j, 3) {
		if (c[j] > (N + j) / 3) { ans = "NO"; }
	}
	cout << ans << endl;

	system("PAUSE");
}


Measured memory_bytes: 760
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pb push_back
#define srt(a) sort(a.begin(),a.end())
#define rsrt(a) sort(a.rbegin(),a.rend())
#define lb(a,b) lower_bound(a.begin(),a.end(),b)
#define ub(a,b) upper_bound(a.begin(),a.end(),b)
#define MOD ((int)(1e9+7))
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define float long double
#define sqrt sqrtl
#define cbrt cbrtl
typedef vector<int> vi;
typedef vector<float> vf;
typedef pair<float,int> fi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<fi> vfi;
typedef vector<vi> vvi;
typedef vector<vf> vvf;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef priority_queue<int> pqi;
typedef priority_queue<ii> pqii;
typedef priority_queue<fi> pqfi;
typedef priority_queue <int, vector<int>, greater<int> > rpqi; 
typedef priority_queue <ii, vector<ii>, greater<ii> > rpqii; 
typedef priority_queue <fi, vector<fi>, greater<fi> > rpqfi; 


int32_t main()
{
	IOS
	int n;cin>>n;
	vector<int>h(n),dp(n);
	for(int i=0;i<n;i++)cin>>h[i];
	dp[0]=0;
	dp[1]=abs(h[0]-h[1]);
	for(int i=2;i<=n;i++)
	{
		dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
	}
	cout<<dp[n-1]<<endl;
}
		


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

using namespace std;

int k, n, a[2*100000];

int main(){
	cin >> k >> n;
	for(int i = 0; i < n; ++i) cin >> a[i];
	int m = 0;
	for(int i = 0; i < n-1; ++i) m = max(m, a[i+1]-a[i]);
	m = max(m, (k-a[n-1])+a[0]);
	cout << k-m << endl;
}

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


void solve () {
    long long n;
    cin >> n;
    int ans = (int) to_string(n).size();
    for (int i = 2; i <= sqrt(n); i++) {
        if(n%i == 0) {
            int x = (int) to_string(n/i).size();
            int y = (int) to_string(i).size();
            ans = min (ans, max (x, y));
        }
    }
    cout << ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}


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

typedef long long ll;
const ll INF = 1e9, MOD = 1e9 + 7;
const double EPS = 1e-9, PI = 3.141592653589793;
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define REPR(i,a,b) for(ll i=b;i>=a;i--)
#define repr(i,n) REPR(i,0,n)
#define all(v) (v).begin(), (v).end()
#define pb push_back

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

    ll a,b,k,cnt=0,ans,num[101];
    cin >> a >> b >> k;
    rep(i,101) num[i] = 0;
    REP(i,1,a+1){
        if(a%i==0 && b%i==0){
            cnt++;
            num[i] = i;
        }
    }
    sort(num,num+101,greater<int>());
    ans = num[k-1];
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
	ll k,a,b; scanf("%lld %lld %lld",&k,&a,&b);
	ll ans = 1;
	if(b-a>2){
		if(k<a-1){
			printf("%d",1+k);
			return 0;
		}
		else{
			k-=(a-1); ans=a;
			int kk = k%2; k/=2;
			ans+=(b-a)*k;
			if(kk) ans++;
		}
	}
	else{
		printf("%d",1+k);
		return 0;		
	}
	printf("%lld",ans);
	return 0;
}

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

#define int long long
#define ll long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<(int)n ; i++)
#define rf(i,n,a) for(int i=n ; i>=a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
#define fill(a,v) memset(a,v,sizeof(a))
#define d1(a) cout << a << "\n"
#define d2(a,b) cout << a << " " << b << "\n"
#define d3(a,b,c) cout << a << " " << b << " " << c << "\n"
#define d4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << "\n"
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);

typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;

int pow(int a, int b, int m)
{
	int ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}

int modinv(int k)
{
	return pow(k, MOD-2, MOD);
}
int ncr(int n, int c){
    int t=1;
    c = min(c,n-c);
    for(int i=1; i<=c ;i++)
    {
     	t= (t*(n-i+1))%MOD;
        t = (t*modinv(i))%MOD;
	}
    return t;
}
int32_t main(){
	fast;
	int n,a,b;
	cin >> n >> a >> b;
	
	int ans = pow(2,n,MOD);

	ans = (ans - ncr(n,a) + n*MOD)%MOD;
	ans = (ans - ncr(n,b) + n*MOD)%MOD;
	ans = (ans - 1 + MOD)%MOD;
	cout << ans;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAX 10005
#define INF 100000000
typedef std::pair<int, int> P;
using namespace std;
 
int a[10][10];
int d[10];

void dij(){
  priority_queue<P, vector<P>, greater<P>> pq;
  for(int i = 0; i < 10; i++) d[i] = INF;
  
  d[1] = 0;
  pq.push(P(0, 1));
  while(!pq.empty()){
    P p = pq.top(); pq.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    for(int i = 0; i < 10; i++){
      if(i == v) continue;
      if(d[i] > d[v] + a[i][v]){
        d[i] = d[v] + a[i][v];
        pq.push(P(d[i], i));
      }
    }
  }
}

int main(){
  int h, w, ans = 0, i, j, k;
  scanf("%d%d", &h, &w);
  for(i = 0; i < 10; i++) for(j = 0; j < 10; j++)
    scanf("%d", &a[i][j]);
  
  dij();
  
  for(i = 0; i < h; i++){
    for(j = 0; j < w; j++){
    scanf("%d", &k);
    ans += (k == -1 ? 0 : d[k]);
    }
  }
  printf("%d\n", ans);
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
   char s[100001];
   scanf("%s",s);

   int point = 0 , g = 0 , p = 0;
   for(int i = 0;s[i] != '\0';i ++){
     if(i%2 == 0){
       if(s[i] == 'p'){
         point --;
       }
     }
     else{
       if(s[i] == 'g'){
         point ++;
       }
     }
   }

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

   return 0;
}

Measured memory_bytes: 256
#float型を許すな
#numpyはpythonで
#dp
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
lis.sort()
print(sum(lis[0:k]))

Measured memory_bytes: 9472
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
using namespace std;
const int mod=998244353;
int n,ans,i,fac[10000005],inv[10000005],fi[10000005];
int qp(int x,int y){
	int z=1;
	while(y){
		if(y&1){
			z=1ll*z*x%mod;
		}
		x=1ll*x*x%mod;
		y/=2;
	}return z;
}
int c(int x,int y){
	return 1ll*fac[x]*fi[y]%mod*fi[x-y]%mod;
}
int main(){
	fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;
	for(i=2;i<=10000000;i++){
		fac[i]=1ll*fac[i-1]*i%mod;
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		fi[i]=1ll*fi[i-1]*inv[i]%mod;
	}
	cin>>n;
	ans=qp(3,n);
	for(i=n/2+1;i<=n;i++){
		ans=(ans+2ll*(mod-c(n,i))*qp(2,n-i))%mod;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 120804
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000001

template <typename T>
struct CHT{

	vector<T> v;
	vector<T> a,b;
	int n;
	long long sign;
	
	T init_value;
	
	CHT(vector<T> &x,T iv,long long s=1){
		init_value = iv;
		sign = s;
		v = x;
		sort(v.begin(),v.end());
		int temp = distance(v.begin(),unique(v.begin(),v.end()));
		v.resize(temp);
		n=1;
		while(true){
			if(n>=v.size())break;
			n<<=1;
		}
		
		v.resize(n,1000000001);
		a.resize(2*n,0);
		b.resize(2*n,init_value);
	}
		
	void add(T A,T B,int start){
		int now = start;
		
		while(true){
			int ll = (now<<(__builtin_clz(now)-__builtin_clz(n)))-n;
			int rr = ll + (n>>(31-__builtin_clz(now))) -1;
			int m = (ll+rr)>>1;
			bool fl = sign*(A*v[ll]+B)<sign*(a[now]*v[ll]+b[now]);
			bool fm = sign*(A*v[m]+B)<sign*(a[now]*v[m]+b[now]);
			bool fr = sign*(A*v[rr]+B)<sign*(a[now]*v[rr]+b[now]);

			if(fl&&fr){
				a[now]=A;
				b[now]=B;
				break;
			}
			if(!fl&&!fr){
				break;
			}
			if(fm){
				swap(A,a[now]);
				swap(B,b[now]);
				swap(fl,fr);
			}
			if(fl){
				now<<=1;
			}
			else{
				now<<=1;
				now++;
			}
		}
	}

	void add_line(T A,T B){
		add(A,B,1);
	}
	
	void add_segment(T A,T B,T L,T R){
		L = distance(v.begin(),lower_bound(v.begin(),v.end(),L));
		R = distance(v.begin(),lower_bound(v.begin(),v.end(),R));
		if(R==L)return;
		L+=n;
		R+=n;
		
		while(true){
			if(L&1){
				add(A,B,L++);
			}
			if(R&1){
				add(A,B,--R);
			}
			if(L>=R)break;
			L>>=1;R>>=1;
		}
	}
	
	T query(T x){
		int now = n + distance(v.begin(),lower_bound(v.begin(),v.end(),x));
		T ret = init_value;
		while(true){
			ret = min(sign*ret,sign*(a[now]*x+b[now]))*sign;
			now>>=1;
			if(now<=0)break;
		}
		return ret;
	}
	
	void show(){
		int n = 1;
		for(int i=1;i<a.size();i++){
			for(int j=0;j<n;j++){
				if(j!=0)cout<<' ';
				cout<<a[i+j];
			}
			cout<<endl;
			i+=n-1;
			n*=2;
		}
	}
	
};

int main(){
	
	int N;
	cin>>N;
	
	long long C;
	cin>>C;
	
	vector<long long> h(N);
	for(int i=0;i<N;i++)cin>>h[i];
	
	CHT<long long> cht(h,Inf);
	
	vector<long long> dp(N,Inf);
	
	for(int i=0;i<N;i++){
		if(i==0){
			dp[i] = 0;
		}
		else{
			dp[i] = h[i]*h[i] + cht.query(h[i]);
		}
		cht.add_line(-2*h[i],h[i]*h[i]+C+dp[i]);
	}
	
	cout<<dp.back()<<endl;
		
	return 0;
}


Measured memory_bytes: 14472
#include <iostream>
#include <string>
#include <stack>
#include <math.h>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;





int main()
{
	int n;
	int sum;
	int k[19];//k[i]???i?????????????¶?????????§??????????????¨?????????????????????
	while (cin >> n) {
		sum = 0;
		if (n > 36) {
			cout << "0" << endl;
		}
		else{
			
			for (int i = 0; i < 19; i++) {
				if (i < 10) {
					k[i] = i + 1;
				}
				else {
					k[i] = 19 - i;
				}
			}
			for (int i = max({0,n-18}); i <= min({ 18,n }); i++) {
				sum += k[i] * k[n - i];
			}
			cout << sum << endl;
		}
		
	}





}

Measured memory_bytes: 1160
package main

import (
	"fmt"
	"sort"
)

type byAbc []rune

func (a byAbc) Len() int           { return len(a) }
func (a byAbc) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a byAbc) Less(i, j int) bool { return a[i] < a[j] }

func main() {
	var s, t string
	fmt.Scan(&s, &t)

	ss := byAbc(s)
	ts := byAbc(t)

	sort.Sort(ss)
	sort.Sort(sort.Reverse(ts))

	ans := ""
	for i := 0; i < min(len(ss), len(ts)); i++ {
		if ss[i] < ts[i] {
			ans = "Yes"
			break
		}
		if ss[i] > ts[i] {
			ans = "No"
			break
		}
	}

	if ans == "" {
		if len(ss) < len(ts) {
			ans = "Yes"
		} else {
			ans = "No"
		}
	}

	fmt.Println(ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}


Measured memory_bytes: 512
#include<stdio.h>
#include<string.h> 
int main(void)
{
   int i;
   int N,K;
   char str[64]={};
 
   scanf("%d",&N);
   scanf("%d",&K);
   scanf("%s",str);
   str[K-1]+=32;
   for(i=0;i<N;i++){
      printf("%c",str[i]);
   }
   printf("\n");
   
   return 0;
}


Measured memory_bytes: 256
from copy import *

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)

def upd(node,x,a):
  y=(len(node)>>1)+x-1
  node[y]=a
  while y:
    y=(y-1)>>1
    node[y]=node[-2](node[(y<<1)+1],node[(y+1)<<1])

def query(node,l_q,r_q,k,l_m,r_m):
  if r_q<=l_m or r_m<=l_q:
    return node[-1]
  if l_q<=l_m and r_m<=r_q:
    return node[k]
  l_a=query(node,l_q,r_q,2*k+1,l_m,(l_m+r_m)//2)
  r_a=query(node,l_q,r_q,2*k+2,(l_m+r_m)//2,r_m)
  return node[-2](l_a,r_a)

H,W,N=map(int,input().split())
S=[[] for i in range(H+1)]
T=[]
init(W+3,T,0,lambda x,y:max(x,y))
X=[tuple(map(int,input().split())) for i in range(N)]
for i in range(N):
  S[X[i][0]].append(X[i][1])
  upd(T,X[i][1]+1,T[(len(T)>>1)+X[i][1]]+1)
P=0
Q=0
for i in range(1,H+1):
  Q=len(S[i])
  for j in range(len(S[i])):
    upd(T,S[i][j]+1,T[(len(T)>>1)+S[i][j]]-1)
  P=max(P,Q+T[0])
  for j in range(len(S[i])):
    upd(T,S[i][j]+1,T[(len(T)>>1)+S[i][j]]+1)
print(P)


Measured memory_bytes: 186028
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 1000000000000000000
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;

int main() {
    ll N;
    cin >> N;
    string s = to_string(N);
    int keta = s.size();
    int ans = 9 * (keta - 1);

    int dp[keta + 1][2][10]; // smaller
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;

    for (int i = 0; i < keta + 1; i++) {
        for (int j = 0; j < 10; j++) {
            if (dp[i][1][j] != -1)
                dp[i + 1][1][9] = max(dp[i + 1][1][9], dp[i][1][j] + 9);
            if (s[i] - '0' != 0) {
                int num = s[i] - '0' - 1;
                dp[i + 1][1][num] = max(dp[i + 1][1][num], dp[i][0][j] + num);
            }
            int num = s[i] - '0';
            dp[i + 1][0][num] = max(dp[i + 1][0][num], dp[i][0][j] + num);
        }
    }

    rep(j, 10) {
        ans = max(ans, dp[keta][0][j]);
        ans = max(ans, dp[keta][1][j]);
    }

    cout << ans << endl;
}

Measured memory_bytes: 3712
#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
using namespace std;
int keep[100][100][100];
int main(){  
  int a,b,c;
  while(cin >> a >> b >> c, a||b||c){
    for(int i = 0;i < 100;i++){
      for(int j = 0;j < 100;j++){
	for(int k = 0;k < 100;k++){
	keep[i][j][k] = 2;
	}
      }
    }

    int n;
    cin >> n;
    vector<int> f(a+b+c,2);
    for(int i =0 ;i < n;i++){
      int at,bt,ct,ans;
      cin >> at >> bt >> ct >> ans;
      keep[at-1][bt-1-a][ct-1-a-b] = ans;
      if(ans == 1){
	f[at-1] = 1;
	f[bt-1] = 1;
	f[ct-1] = 1;
      }
    }
    
    for(int i = 0;i < a;i++){
      for(int j = a;j < a+b;j++){
	for(int k = a+b;k < a+b+c;k++){
	  if(keep[i][j-a][k-b-a] == 0){
	    if(f[i] == 2 && f[j] == 1 && f[k] == 1){
	      f[i] = 0;
	    }
	    if(f[i] == 1 && f[j] == 2 && f[k] == 1){
	      f[j] = 0;
	    }
	    if(f[i] == 1 && f[j] == 1 && f[k] == 2){
	      f[k] = 0;
	    }
	  }
	}
      }
    }
    for(int i =0;i < f.size();i++){
      cout << f[i] << endl;
    }
  }
  
  return 0;
}
vector<string> split(string str,string delim){
  vector<string> items;
  size_t dlm_idx;
  if(str.npos == (dlm_idx = str.find_first_of(delim))){
    items.push_back(str.substr(0,dlm_idx));
  }
  while(str.npos != (dlm_idx = str.find_first_of(delim))){
    if(str.npos == str.find_first_not_of(delim)){
      break;
    }
    items.push_back(str.substr(0,dlm_idx));
    dlm_idx++;
    str = str.erase(0,dlm_idx);
    if(str.npos == str.find_first_of(delim) && "" != str){
      items.push_back(str);
      break;
    }
  }
  return items;
}

Measured memory_bytes: 5104
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#define debug(x) cerr<<#x<<':'<<x<<endl
using namespace std;
inline long long read()
{
	long long ans=0,f=1;
	char c=getchar();
	while (!isdigit(c))
	{
		if (c=='-')
			f=-1;
		c=getchar();
	}
	while (isdigit(c))
	{
		ans=(ans<<3)+(ans<<1)+(c^48);
		c=getchar();
	}
	return ans*f;
}
void write(long long x)
{
	if (x>=10)
	{
		write(x/10);
		x%=10;
	}
	putchar(x+'0');
}
long long count(long long n,long long k)
{
	long long s=n/k;
	return s*s*s;
}
int main()
{
	long long n,k;
	n=read(),k=read();
	long long ans=count(n,k);
	if (k%2==0)
		ans+=count(n+k/2,k);
	write(ans);
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
const long long inf = 1e17+7;
int p[5005];
long long c[5005];
int vis[5005];
long long a[10005];
long long sum[10005];

//2*n
long long solve(int n,long long k){
    for(int i = n+1; i <= 2*n; i++) a[i] = a[i-n];
    sum[0] = 0;
    for(int i = 1; i <= 2*n; i++){
        sum[i] = sum[i-1]+a[i];
    }
    long long cycle = sum[n];
    long long ans = -inf;
    for(int i = 1; i <= 2*n; i++){
        for(int j = i; j<=2*n && j-i+1<=k; j++){
            long long cur = sum[j]-sum[i-1];
            long long left = k-(j-i+1);
            if(cycle>0) cur += left/(long long)n*cycle;
            if(cur>ans) ans = cur;
        } 
    }
    return ans;
}

int main(){
    int n; long long k;
    scanf("%d%lld",&n,&k);
    for(int i = 1; i <= n; i++) scanf("%d",&p[i]);
    for(int i = 1; i <= n; i++) scanf("%lld",&c[i]);
    long long ans = -inf;
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        else{
            int cur = i, size = 0;
            while(vis[cur]==0){
                vis[cur] = 1;
                a[++size] = c[cur];
                cur = p[cur];
            }
            long long res = solve(size,k);
            if(res>ans) ans = res;
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 1968
#include <bits/stdc++.h>
#define ll long long int
#define all(x) x.begin(), x.end()
using namespace std;
ll power(ll x, ll y,ll  m) 
{ 
    if (y == 0) 
        return 1; 
    ll  p = power(x, y/2, m) % m; 
    p = (p * p) % m; 
  
    return (y%2 == 0)? p : (x * p) % m; 
} 
ll modInverse(ll a, ll m) 
{ 
    ll g = __gcd(a, m); 
    if (g != 1) 
        cout << "Inverse doesn't exist"; 
    
    
        // If a and m are relatively prime, then modulo inverse 
        // is a^(m-2) mode m 
        
              return power(a, m-2, m); 
    
} 
ll fact[1000];
void fac(ll m)
{
	ll i;
	fact[0]=1;
	for(i=1;i<1000;i++)
	{
		fact[i]=(i*fact[i-1])%m;
	}
}

ll comb(ll n,ll k,ll m)
{
	return(fact[n]*modInverse(fact[k],m)%m *modInverse(fact[n-k],m)%m)%m;
}
bool cmp(pair<ll,ll> a,pair<ll,ll>b)
{
	if(a.second==b.second)
	return a.first<b.first;
	return a.second>b.second;
}
int main () {
ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  ll n;
  cin>>n;
  ll i;
  ll a[n];
  for(i=0;i<n;i++)
  cin>>a[i];
  ll ans;ans=0;
  ll m=a[0];
  for(i=1;i<n;i++)
  {
  	if(a[i]>=m)
  	{
  		m=a[i];
	  }
	  else
	  {
	  	ans+=m-a[i];
	  }
  }
cout<<ans<<endl;
return 0;
}


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

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

	if (A+B == C+D) {
		cout << "Balanced " << endl;
	}
	else if (A+B > C+D) {
		cout << "Left" << endl;
	}
	else {
		cout << "Right" << endl;
	}
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
int i;
int a,b,n,sum;
while(scanf("%d%d%d",&a,&b,&n)!=-1){
a%=b;
sum=0;
for(i=0;i<n;i++){
sum+=a*10/b;
a=a*10%b;
}
printf("%d\n",sum);
}
return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,k;
  cin >> n >> k;
  int sum=1;
  int x=n;
  for(int i=0;i<n;i++) {
    if(x/k==0) {
      sum+=0;
      break;}
    else {
      x/=k;
      sum+=1;}
    }
  cout << sum << endl;
  return 0;
  }

Measured memory_bytes: 256
#include<stdio.h>

int tenki(const char s[3], const char t[3]){
    int i;
    int tmp = 0;

    for(i = 0; i < 3; i++){
        if(s[i] == t[i]){
            tmp++;
        }
    }

    return tmp;
}

int main(void){
    char s[3];
    char t[3];

    scanf("%s", s);
    scanf("%s", t);

    printf("%d", tenki(s, t));

    return 0;
}

Measured memory_bytes: 128
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    wa, wb, sa, sb, sol, lim = list(map(int, readline().split()))
    wa *= 100
    wb *= 100

    water = []
    sugar = []

    for wac in range(lim // wa + 1):
        cw = wa * wac
        for wbc in range(30):
            wadd = cw + wb * wbc
            if wadd <= lim:
                water.append(wadd)
            else:
                break

    for sac in range(3001):
        cs = sa * sac
        if cs > lim:
            break
        for sbc in range(3001):
            sadd = cs + sb * sbc
            if sadd <= lim:
                sugar.append(sadd)
            else:
                break

    water = list(set(water))
    sugar = list(set(sugar))
    water.sort()
    sugar.sort()

    import bisect

    maxconc = 0
    ans = [0] * 2

    for ww in water[1:]:
        res = min(sol * ww // 100, lim - ww)
        if res < 0:
            continue

        idx = bisect.bisect_right(sugar, res) - 1

        if idx >= 0:
            sw = sugar[idx]

        conc = (100 * sw) / ww

        if conc >= maxconc:
            maxconc = conc
            ans[0] = (ww + sw)
            ans[1] = sw

    print(*ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 52480