akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
ll gcd(ll a,ll b)
{
    if(a%b==0)
    {
        return b;
    }
    else
    {
        return gcd(b,a%b);
    }
}
ll com(ll a,ll b,ll m)
{
    ll temp=a%m;
    if((temp+m)%m>b)
    {
        b+=m;
    }
    ll ans=a+b-(temp+m)%m;
    return ans;
}
int main()
{
    int T;
    ll a,b,c,d;
    scanf("%d",&T);
    while(T--)
    {
        cin>>a>>b>>c>>d;
        if(b>a)
        {
            printf("No\n");
        }
        else if(d<b)
        {
            printf("No\n");
        }
        else
        {
            ll po=gcd(b,d);
            if(com(c-b+1,a%po,po)>=0)
            {
                printf("Yes\n");
            }
            else
            {
                printf("No\n");
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;typedef long long ll;typedef vector<ll> vl;typedef vector<vl> vvl;typedef pair<ll,ll> pl;typedef vector<pl> vp;const ll INF=1001001001;const ll LINF=1001001001001001001;const ll D4[]={0,1,0,-1,0};const ll D8[]={0,1,1,0,-1,-1,1,-1,0};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;}
#define fore(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

ll d(ll src,ll to,ll x,ll y){
    ll ret=abs(to-src);
    chmin(ret,abs(to-x)+abs(y-src)+1);
    chmin(ret,abs(src-x)+abs(y-to)+1);
    return ret;
}
void solve(long long N, long long X, long long Y){
    vl ans(N);
    rep(i,N)fore(j,i+1,N-1){
        ans[d(i,j,X-1,Y-1)]++;
    }
    fore(i,1,N-1){
        cout<<ans[i]<<endl;
    }
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long X;
    scanf("%lld",&X);
    long long Y;
    scanf("%lld",&Y);
    solve(N, X, Y);
}


Measured memory_bytes: 256
#include <iostream>

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

   int sum = 0;
   if(A<B) sum += A; 
   else sum += B;
   if(C<D) sum += C; 
   else sum += D;

   std::cout << sum << std::endl;

   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int, int>
#define vi vector<int>
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define x first
#define y second
#define rep(i, j, k) for(i=j; i<k; i++)
#define sep(i, j, k) for(i=j; i>k; i--)
const int N = 2e5+5, inf = 1e9+7;
int n, k, i, j;
int A[21][21], dp[1<<21];

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int i, j, a, b, ans = 0;
    cin>>n;
    rep(i, 0, n) rep(j, 0, n) cin>>A[i][j];
    dp[0] = 1;
    rep(i, 0, 1<<n){
        dp[i]%=inf;
        a = __builtin_popcount(i);
        rep(j, 0, n) if(!(i>>j&1) && A[j][a])
            dp[i|(1<<j)] += dp[i];
    }
    cout<<dp[(1<<n)-1];
}

Measured memory_bytes: 16768
#include <stdio.h>
int main(void){
    int e[101][101];
    int R, C, r, c;
    int s, total;
    
    scanf("%d %d", &R, &C);
    for(r=1; r<=R; r++){
        for(c=1; c<=C; c++) scanf("%d", &e[r][c]);
    }
    
    for(r=1; r<=R; r++){
        s=0;
        for(c=1; c<=C; c++) s +=e[r][c];
        e[r][0]=s;
    }
    total =0;
    for(c=1; c<=C; c++){
        s=0;
        for(r=1; r<=R; r++) s+=e[r][c];
        e[0][c]=s;
        total += s;
    }
    for(r=1; r<=R; r++){
        for(c=1; c<=C; c++) printf("%d ", e[r][c]);
        printf("%d\n",e[r][0] );
    }
    for(c=1; c<=C; c++) printf("%d ", e[0][c]);
    printf("%d\n", total);
    return 0;
}



Measured memory_bytes: 2048
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        long sum = 0;
        for (int i = 0; i < s.length(); i++) {
            sum += s.charAt(i) - '0';
        }
        if (sum % 9 == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }
}

Measured memory_bytes: 41592
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
const int N = 300100;
int op(int a,int b){
  return max(a,b);
}
int e(){
  return 0;
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,k,a;
  cin >> n >> k;
  segtree<int,op,e> seg(N);
  for(int i = 0; i < n; ++i){
    cin >> a;
    int l = max(0,a-k),r = min(N,a+k+1);
    int ai = seg.prod(l,r);
    seg.set(a,ai+1);
  }
  cout << seg.all_prod();
  return 0;
}

Measured memory_bytes: 8516
n,m = map(int, input().split())
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
base1 = 0
base2 = 0
if n >= 2:
    base1 = comb(n,2)
if m >= 2:
    base2 = comb(m,2)
ans = base1 + base2
print(ans)


Measured memory_bytes: 3060
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;

int H, W, A, B;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> H >> W >> B >> A;
	for (int i = 1; i <= H; i++){
		for (int j = 1; j <= W; j++){
			if (i <= A && j <= B) cout << 0;
			else if (i > A && j > B) cout << 0;
			else cout << 1;
		}
		cout << '\n';
	}













	return 0;
}


Measured memory_bytes: 1280
s = gets.to_i

n = 0
step = 1
digit = 1
stack = []
start = 0

loop {
	over = false
	(start..9).each{|k|
		f = -> d {(n + step) / d - n / d}
		addition = digit * (step - f[3] - f[5] + f[15]) + 4 * (f[3] + f[5]) 
		
		if s <= addition
			stack << k
			over = true
			start = 0
			break
		else
			s -= addition
			n += step
			start = 1
		end
	}
	
	if over
		step /= 10
		break if step == 0
	else
		step *= 10
		digit += 1
	end
}

x = stack.join.to_i + 1
str = (x..x+9).map{|i|
	i % 15 == 0 ? "FizzBuzz" :
	i % 3 == 0 ? "Fizz" :
	i % 5 == 0 ? "Buzz" :
	i
}.join

puts str[s-1..s+18]

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	ll a, b, k;
	cin >> a >> b >> k;

	while(true){
		if(a % 2 == 1){
			a--;
		}
		b += a/2;
		a -= a/2;
		k--;
		if(k == 0) break;

		if(b % 2 == 1){
			b--;
		}
		a += b/2;
		b -= b/2;
		k--;
		if(k == 0) break;
	}

	cout << a << " " << b << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <climits>

using namespace std;
using ll  = long long;
template <typename T> T In() {
    T t;
    cin >> t;
    return t;
}
template <typename T> vector<T> ReadVec1(int N) {
    vector<T> vec(N);
    for(int i = 0; i < N; i++)
        vec[i] = In<T>();
    return move(vec);
}
template <typename T> vector<vector<T>> Vec2(int i, int j, T ini = 0) {
    vector<vector<T>> vec(i, vector<T>(j, ini));
    return move(vec);
}
template <typename T> vector<vector<vector<T>>> Vec3(int i, int j, int k, T ini = 0) {
    vector<vector<vector<T>>> vec(i, vector<vector<T>>(j, vector<T>(k, ini)));
    return move(vec);
}

int main() { 
    int N = In<int>();
    int K = In<int>();
    vector<int> h = ReadVec1<int>(N);
    vector<int> dp(N);
    for(int n = 1; n < N; n++){
        int dpn = INT_MAX;
        for(int k = 1; k <= min(K,n); k++){
            dpn = min(dpn, dp[n - k] + abs(h[n - k] - h[n]));
        }
        dp[n] = dpn;
    }
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<map>
#include<utility>
#include<queue>
using namespace std;
typedef pair<long, long> P;
typedef priority_queue<P, vector<P>, greater<P>> Q;

int D_MAX = 1e8;
int n, x, d;
map<int, Q> m;

int main() {
    scanf("%d %d %d", &n, &x, &d);
    if (d == 0) {
        printf("%d\n", (x == 0) ? 1 : n + 1);
        return 0;
    }
    if (d < 0) {
        x = -x; d = -d;
    }
    for (int i = 0; i <= n; i++) {
        int y = static_cast<long>(x) * i % d;
        if (y < 0) y = y + d;
        long z = static_cast<long>(x) * i / d;
        if (y != 0 && x < 0) z--;
        long ma = static_cast<long>(2 * n - 1 - i) * i / 2;
        long mi = static_cast<long>(i - 1) * i / 2 - 1;
        m[y].emplace(P(mi + z, ma + z));
    }
    long ans = 0;
    for (auto &i : m) {
        Q q = i.second;
        while (true) {
            P p1 = q.top(); q.pop();
            if (q.empty()) {
                ans += p1.second - p1.first;
                break;
            }
            P p2 = q.top(); q.pop();
            if (p1.second >= p2.second) q.emplace(p1);
            else if (p1.second >= p2.first) q.emplace(P(p1.first, p2.second));
            else {
                q.emplace(p2);
                ans += p1.second - p1.first;
            }
        }
    }
    
    printf("%ld\n", ans);
    return 0;
}


Measured memory_bytes: 22144
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;

// ABC161-A
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		int z = sc.nextInt();

		Map<String, Integer> map = new LinkedHashMap<>();
		map.put("A", x);
		map.put("B", y);
		map.put("C", z);

		// A <-> B
		int a = map.get("A");
		int b = map.get("B");
		map.put("A", b);
		map.put("B", a);

		// A <-> C
		int a2 = map.get("A");
		int c = map.get("C");
		map.put("A", c);
		map.put("C", a2);

		for (Integer num : map.values()) {
			System.out.print(num + " ");
		}

		sc.close();
	}
}


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

const int size=100010;
int n,m;
int used[size];
int d[size];
bool flag=false;
struct edge//from left to right
{
 	int to,val;
 	edge(int to=0,int val=0):to(to),val(val) {}
 };

vector<edge> V[size];

void dfs(int from,int to,int len)
{
 	if(used[to])
 		if(d[from]+len!=d[to])
 		{
		 	cout<<"No"<<endl;
		 	exit(0);
			}
		else return;
		
	used[to]=1;
	d[to]=d[from]+len;
	for(int i=0;i<V[to].size();i++)
	{
		int nto=V[to][i].to;
		dfs(to,nto,V[to][i].val);
		}
	} 

int main()
{
	cin>>n>>m;
	if(m==0)
	{
		cout<<"Yes"<<endl;
		return 0;
		}	
	
	for(int i=0;i<m;i++)
	{
		int L,R,len;
		cin>>L>>R>>len;
		V[L].push_back(edge(R,len));
		V[R].push_back(edge(L,-len));
		}
	for(int i=1;i<=n;i++)
		if(!used[i])
			dfs(i,i,0);
	cout<<"Yes"<<endl;		
 	return 0;
 }

Measured memory_bytes: 12416
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using Pt = pair<int, int>;

void ABC172B()
{
	string S;
	string T;
	cin >> S;
	cin >> T;
	int ct = 0;
	for (int i = 0; i < S.size(); ++i)
	{
		if (S[i] != T[i])
			++ct;
	}
	cout << ct << endl;
}

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

Measured memory_bytes: 3916
#include <iostream>
#include <cmath>
#include <vector>
#include <list>
#include <string>
#include <algorithm>

using namespace std;
typedef long long ll;

int main() {
    int N,Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<ll> csum(N+10);
    int jg=0;
    for(int i=0;i<N;i++){
        int ct=0;
        if(S[i]=='A') jg=1;
        else if(jg==1 && S[i]=='C'){
            jg=0;
            ct=1;
        }
        else jg=0;
        csum[i+1]=csum[i]+ct;
    }
    int r[Q],l[Q];
    for(int i=0;i<Q;i++){
        cin >> l[i] >> r[i];
    }
    for(int i=0;i<Q;i++){
        if(l[i]==1){
            cout << csum[r[i]] << endl;
        }else{
            cout << csum[r[i]]-csum[l[i]] << endl;
        }
    }
}

Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(){
    int n,m;
    cin >> n >> m;
    int maxl=0,minr=1e9;
    for(int i=0; i<m; i++){
        int l,r;
        cin >> l >> r;
        maxl=max(l,maxl);
        minr=min(r,minr);
    }
    int cnt=0;
    for(int i=1; i<=n; i++){
        if(i>=maxl && i <= minr)
            cnt++;
    }
    cout << cnt;
    return 0;
}

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

int main(){
	int n;
	scanf("%d", &n);
	int i=1;
	int answer=-1;
	while(i<10){
		if((n%i == 0) && (n/i >= 1) && (n/i <=9)) answer = 1;
		i++;
	}
	
	if(answer == 1) printf("Yes\n");
	else printf("No\n");
	
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(u, vis) memset(u, vis, sizeof(u))
#define ll long long
#define ull unsigned long long
#define MOD  1000000007
#define MAX  1e9
#define pb   push_back
#define F    first
#define S    second

void LCS(string a, string b, ll n,ll m){
	vector<vector<ll>> dp(n+1, vector<ll>(m+1,0));
	for(ll i = 1; i <= n; ++i){
		for(ll j = 1; j <= m; ++j){
			if(a[i-1] == b[j-1]){
				dp[i][j] = dp[i-1][j-1] +1;
			}
			else dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
		}
	}
	ll i = n, j = m;
	ll val = dp[n][m];
	char arr[val];
	while(i>0 && j>0){
		if(a[i-1] == b[j-1]){
			arr[val-1] = a[i-1];
			// cout<<arr[val-1]<<" "<<a[i-1]<<endl;
			val--;
			i--;
			j--;
		}
		else if(dp[i-1][j] > dp[i][j-1])
			i--;
		else j--;

	}
	// cout<<arr[0]<<arr[1]
	for(ll i = 0 ; i < dp[n][m]; ++i){
		cout<<arr[i];
	}

}

signed main() {
	ll t=1;
	//cin>>t;
	while(t--){
		string s1,s2;
		cin>>s1>>s2;
		LCS(s1, s2, s1.length(), s2.length());
		
	}
	
}

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

minv = 1 << 30

def digit_sum(n):
	lst = list(map(int, str(n)))
	return sum(lst)

for i in range(1, n//2 + 1):
	a = i
	b = n - i
	minv = min(digit_sum(a) + digit_sum(b), minv)

print(minv) 


Measured memory_bytes: 42088
import sys
input = sys.stdin.buffer.readline

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

def dist(xy1, xy2):
  x1, y1 = xy1
  x2, y2 = xy2
  return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

tmp = 0
for i in range(N):
  for j in range(i + 1, N):
    tmp += dist(XY[i], XY[j]) / (N / 2)

print(tmp)

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

using namespace std;

struct Info{int w,s,e;};
vector<Info> V;

int out(int n, int& on,int p){
  int s = 0;

  for(int i = p-on+1; i <= p; i++){
  }
}
bool compare(const Info& in1, const Info& in2){
  if(in1.s != in2.s) return in1.s < in2.s;
  return in1.e < in2.e;
}

int main(){
  int n;
  while(cin >> n && n){
    V.clear();

    for(int i = 0; i < n; i++){
      Info info;
      cin >> info.w >> info.s >> info.e;
      V.push_back(info);
    }

    sort(V.begin(),V.end(),compare);

    int sum = 0,now = 0;
    vector<Info> on;
    bool ans = true;

      //in
      for(int i = 0; i < V.size(); i++){
	now = V[i].s;
	on.push_back(V[i]);
	sum += V[i].w;
	//out

	for(vector<Info>::iterator j = on.begin(); j < on.end(); j++){
	  if(j->e <= now){
	    sum -= j->w;
	    on.erase(j);
	    j--;
	  }
	}
	if(sum > 150){
	  ans = false;
	  break;
	}
      }
      if(ans) cout << "OK" << endl;
      else cout << "NG" << endl;
  }
  return 0;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int> 
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int n,ans;
int a[100001];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        ans=__gcd(ans,a[i]);
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18+10;
const int mod = 1e9+7;
const int N = 22;
using ll = long long;
int n,dp[N][5000000];
bool arr[N][N];
int add(int a, int b) {
    a = (a + b) % mod;
    if(a < 0) a += mod;
    return a;
}
int lim; 
int check(int i, int mask) {
    if(i == n && mask == lim) return 1;
    if(dp[i][mask] != -1) return dp[i][mask];
    int ans = 0;
    for(int j = 0; j < n; j++) {
        if(arr[i][j] && ((mask & (1 << j))==0)) {
            ans = (ans + check(i+1, mask | (1 << j))) % mod;
        }
    }
    return dp[i][mask] = ans;
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) scanf("%d", &arr[i][j]);
    }
    lim = (1<<n) -1;
    memset(dp, -1, sizeof(dp));
    dp[n][lim] = 1;
    /*for(int i = n-1; i >= 0; i--) {
        for(int mask = 0; mask <= lim; mask++) {
            for(int j = 0; j < n; j++) {
                if(arr[i][j] && ((mask & (1 << j)) == 0)) {    //brackets?
                    dp[i][mask] = (dp[i][mask] + dp[i+1][mask | (1 << j)]) % mod;
                }
            }
        }
    }*/
    for(int i = 0;0 && i <= n; i++) {
        for(int j = 0; j <= lim; j++) {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
    cout << check(0, 0);
    //printf("%d\n", dp[0][0]);
    return 0;
}

//dp[2][1] += (dp[1][2])

/*

  0 1 2 3 4 5 6 7           
---------------             0 -> 000
0.3 0 0 0 0 0 0 0           1 -> 001
1.0 1 2 0 1 0 0 0           2 -> 010
2.0 0 0 1 0 1 1 0           3 -> 011
3.0 0 0 0 0 0 0 1           4 -> 100
                            5 -> 101
                            6 -> 110
                            7 -> 111



*/

Measured memory_bytes: 433368
#include<iostream>
#include<vector>
#include<cstddef>
#include<algorithm>
using ui = std::uint32_t;

int main(){
	ui n, w;
	std::cin >> n >> w;

	std::vector<std::vector<ui>>
		tab( n + 1, std::vector<ui>( w + 1, 0 ) );

	using item = std::pair<ui, ui>;//v,w
	std::vector<item> items( n );
	for( auto& e : items )
		std::cin >> e.first >> e.second;


	for( ui i{ 1 }; i <= n; ++i )
	{
		const auto& item_ = items[i - 1];
		for( ui j{}; j <= w; ++j )
		{

			if( j - item_.second <= w )
				tab[i][j]
					= std::max( tab[i-1][j]
							, tab[i-1][j - item_.second] + item_.first );
			else
				tab[i][j] = std::max( tab[i][j], tab[i - 1][j] );
			
		}

	}
	/*
	for( auto& e : tab )
	{
		for( auto& ee : e )
			std::cout << ee << " ";
		std::cout << "\n";
	}
	*/
	std::cout << tab[n][w] << "\n";
	return 0;
}


Measured memory_bytes: 6828
#include <iostream>
#include <array>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <climits>
#include <string.h>
#include <cctype>
#include <set>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

// a と b の最大公約数を返す関数
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

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

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll 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 { return mint(*this) += a; }
	mint operator-(const mint a) const { return mint(*this) -= a; }
	mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

struct combination {
	vector<mint> fact, ifact;
	combination(int n) :fact(n + 1), ifact(n + 1) {
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
		ifact[n] = fact[n].inv();
		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return fact[n] * ifact[k] * ifact[n - k];
	}
} comb(2000005);

mint g(int r, int c) {
	return comb(r + c + 2, r + 1) - 1;
}

bool comp(int i, int j) {
	return i > j;
}

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}


int main()
{
	long long w, h, x, y;
	cin >> w >> h >> x >> y;
	cout << ((long double)w * h * 0.5) << " " << (w / 2.0 == x && h / 2.0 == y ? 1 : 0);
}



Measured memory_bytes: 31488
using System;
using System.Text;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] V = new int[N];
		string[] s = Console.ReadLine().Split(' ');
		for (int i = 0; i < N; i++)
        {
           
           V[i] = int.Parse(s[i]);
        }
        int[] C = new int[N];
		string[] t = Console.ReadLine().Split(' ');
		for (int j = 0; j < N; j++)
        {
            
            C[j] = int.Parse(t[j]);
        }

        int[] d = new int[N];
        for(int k = 0; k < N; k++)
        {
            d[k]=V[k] - C[k];
        }

        int ans = 0;
        for(int i = 0; i < N; i++)
		{
			if (d[i] > 0) { ans = ans + d[i]; }

		}

		Console.WriteLine(ans);
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <complex>
#include <functional>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(c,i) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

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

int main()
{
	map<char,int> table;
	table['I']=1;
	table['V']=5;
	table['X']=10;
	table['L']=50;
	table['C']=100;
	table['D']=500;
	table['M']=1000;
	for(string s;cin>>s;){
		int res=0;
		rep(i,s.size()){
			if(i==s.size()-1)
				res+=table[s[i]];
			else if(table[s[i]]>=table[s[i+1]])
				res+=table[s[i]];
			else
				res-=table[s[i]];
		}
		cout<<res<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>

using namespace std;

int main(void){
    int N, M, C;
    cin >> N >> M >> C;
    vector<int> B(M);
    vector<vector<int>> A(N, vector<int>(M));
    for(int i = 0; i < M; i++) cin >> B[i];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++) cin >> A[i][j];
    }
    int ans = 0;
    for(int i = 0; i < N; i++){
        int lhs = C;
        for(int j = 0; j < M; j++) lhs += A[i][j] * B[j];
        if(lhs > 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;

int main()
{
	int n;	cin >> n;
	
	vector <int> a(n);
	for(int& x : a)	scanf("%d", &x);
	
	ll Ans = 0;
	map <int,int> Cnt;
	
	for(int i = 0; i < n; i++)
	{
		Ans += (ll) Cnt[a[i] - i];
		Cnt[-a[i] - i]++;
	}
	
	cout << Ans << endl;
}

Measured memory_bytes: 21208
/**
 *  author: andychen
 *  created: 09.19.2020 22:51:54
**/

#include <bits/stdc++.h>

using namespace std;

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

    if (s[s.length() - 1] == 's')
        cout << s + "es\n";
    else
        cout << s + "s\n"; 

    return 0;
}


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

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

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define up(i, a, b) for (int i = (a); i <= (b); i++)
#define down(i, a, b) for (int i = (a); i >= (b); i--)
#define mem(x, y) memset(x, (y), sizeof x)
#define ff first
#define ss second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define sc(a) scanf("%d", &a)
#define scl(a) scanf("%lld", &a)
#define scs(a) scanf("%s", a)
#define pr(a, b) printf("%d%c", a, b)
#define prl(a, b) printf("%lld%c", a, b)
#define PQ priority_queue
#define ld long double
#define all(v) v.begin(), v.end()
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> V;

char s[100010];
ll dp[100010][15],mod=1e9+7;
int main(){
	scs(s+1);
	int n=strlen(s+1);
	dp[0][0]=1;
	up(i,1,n){
		if(s[i]=='?')up(o,0,12)up(p,0,9)dp[i][(o*10+p)%13]=(dp[i][(o*10+p)%13]+dp[i-1][o])%mod;
		else {
			int c=s[i]-'0';
			up(o,0,12)dp[i][(o*10+c)%13]=(dp[i][(o*10+c)%13]+dp[i-1][o])%mod;
		}
	}
	prl(dp[n][5],'\n');
}

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

#define step(i, s, n, d) for(int i=s; i<n; i+=d)
#define FOR(i,s,n) step(i,s,n,1)
#define rep(i,n) FOR(i,0,n)
#define gets(x) x; cin >> x;
#define puts(x) x; cout << x << endl;
#define list_input(x, n) x[n]; rep(i,n){ gets(x[i]);}
#define ll long long

int main(){
  int n;
  cin >> n;
  string s[n];
  int result = 1;
  list_input(s, n)
  sort(s, s+n);
  rep(i, n-1){
    if (s[i] != s[i+1]) {
      result += 1;
    }
  }
  if (result == 4) {
    puts("Four")
  }else{
    puts("Three")
  }
}


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

int main(){

	bool is_prime[50000];
	
	is_prime[0]=is_prime[1]=false;
	for(int i=2;i<50000;i++){
		is_prime[i]=true;
	}
	
	for(int i=2;i*i<50000;i++){
		if(is_prime[i]){
			for(int j=i*i;j<50000;j+=i){
				is_prime[j]=false;
			}
		}
	}
	
	
	while(true){
		int n;
		cin>>n;
		int count=0;
		
		if(n==0)
			break;
		
		for(int i=2;i<=(n/2);i++){
			if(is_prime[i]&&is_prime[n-i]){
				count++;
			}
		}
		
		cout<<count<<endl;
		}
	
	
	return 0;
	
}

Measured memory_bytes: 3064
# include <bits/stdc++.h>
using namespace std;
int main(){
	int n , count = 0;
	string s;
	cin >> n >> s;
	for(int i = 0; i < n; i ++){
		char c = s[i];
		while(i + 1 < n && c == s[i + 1]) ++ i;
		count ++;
	}
	cout << count << "\n";
}

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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

  string s;cin>>s;

  if(count(s.begin(), s.end(), 'A') > 0 && count(s.begin(), s.end(), 'B') > 0) {
    puts("Yes");
  }else
  {
    puts("No");

  }
  

  
  return 0;
}


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

int main(){
    int k;
	string s; cin>>s>>k;
	vector<set<int>> a(26);
	rep(i,s.size()) a[s[i]-'a'].insert(i);

	set<string> ans;
	rep(p,26){
	    range(l,1,k+1){
    	    for(auto i:a[p]) if(i+l<=s.size()) ans.insert(s.substr(i,l));
	    }
	    if(ans.size()>=k) break;
	}
	auto itr=ans.begin();
	rep(i,k-1)itr++;
    cout<<*itr<<endl;
	return 0;
}


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

int main() {
	int ans = 0;
	for (int i = 0; i < 5; ++i) {
		int x;
		cin >> x;
		if (x == 0) {
			ans = i + 1;
		}
	}

	cout << ans;
	
	return 0;
}
	

Measured memory_bytes: 3568
s = input()
t = input()
S = sorted(list(s))
T = sorted(list(t),reverse = True)
s1 = "".join(S)
s2 = "".join(T)
if sorted([s1,s2])[0] == s1 and s1 != s2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
s = input()
t = input()

def gcd(a,b):
    if a<b:
        a,b = b,a
    if b==0:
        return a
    c = a%b
    return gcd(b,c)

def lcm(a,b):
    return a*b//gcd(a,b)

l = lcm(n,m)

for i in range(n):
    if i*m%n==0:
        j = i*m//n
        if s[i]!=t[j]:
            print(-1)
            exit()
print(l)

# for i in range(n):
#     ls[i*l//n] = s[i]
# for i in range(m):
#     if ls[i*l//m]!="." and ls[i*l//m]!=t[i]:
#         print(-1)
#         exit()
# print(l)


Measured memory_bytes: 3316
#include <climits>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <set>

using namespace std;


int main()
{
	int n;
	scanf("%d", &n);
	int m;
	scanf("%d", &m);
	int c;
	scanf("%d", &c);

	int * b = new int[m];

	for (size_t i = 0; i < m; i++)
	{
		scanf("%d", &b[i]);
	}
	int count = 0;
	for (size_t i = 0; i < n; i++)
	{
		int tmp = c;
		for (size_t j = 0; j < m; j++)
		{
			int a;
			scanf("%d", &a);
			tmp += a * b[j];
		}
		if (tmp > 0) count++;
	}

	printf("%d\n", count);
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace Application
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var x = new int[n];
            var y = new int[n];

            for (int i = 0; i < n; i++)
            {
                var xy = Console.ReadLine().Split();
                x[i] = int.Parse(xy[0]);
                y[i] = int.Parse(xy[1]);
            }

            var p = new int[n];
            for (int i = 0; i < n; i++) p[i] = i;

            var sum = 0.0;
            perm(p, item =>
            {
                var a = item[0];
                for (int i = 1; i < item.Length; i++)
                {
                    var b = item[i];
                    sum += distance(x[a], y[a], x[b], y[b]);
                    a = b;
                }
            });

            var f = fact(n);
            Console.WriteLine(sum / f);
        }

        static double fact(double n)
        {
            var ans = 1.0;
            for (double i = 2; i <= n; i++) ans *= i;
            return ans;
        }

        static double distance(int x1, int y1, int x2, int y2)
        {
            return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
        }

        static void perm<T>(T[] v, Action<T[]> f)
        {
            perm(v, new T[v.Length], new bool[v.Length], 0, f);
        }

        static void perm<T>(T[] d, T[] a, bool[] v, int n, Action<T[]> f)
        {
            if (d.Length <= n)
            {
                f(a);
                return;
            }

            for (int i = 0; i < d.Length; i++)
            {
                if (v[i]) continue;
                v[i] = true;
                a[n] = d[i];
                perm(d, a, v, n + 1, f);
                v[i] = false;
            }
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
#define maxn 205
#define inf 1000000000
int n,m,r;
struct node
{
    int to,dis;
};
vector<node> g[maxn];
int v[maxn],d[maxn][maxn];
int tmp[10];
int ans;
bool vis[10];
void backtrack(int now)
{
    if(now==r+1)
    {
        int t=0;
        for(int i=1;i<n;i++)t+=d[tmp[i]][tmp[i+1]];
        ans=min(ans,t);
        return ;
    }
    for(int i=1;i<=r;i++)if(!vis[i])
    {
        vis[i]=1;tmp[now]=v[i];
        backtrack(now+1);
        vis[i]=0;
    }
}
main()
{
    scanf("%d%d%d",&n,&m,&r);
    for(int i=1;i<=r;i++)scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=inf;
    for(int i=1;i<=n;i++)d[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        g[x].push_back({y,z}),g[y].push_back({x,z});
        d[x][y]=d[y][x]=z;
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }
    ans=inf;
    backtrack(1);
    printf("%d\n",ans);
    return 0;
}



Measured memory_bytes: 896
#include<stdio.h>

int main(void){

    int a,n,i,min=1000000,max=-1000000;
    long int sum=0;
    scanf("%d",&n);

    for(i=0;i<n;i++){
        scanf("%d",&a);
        sum+=a;

        if(min>a)
            min=a;
        if(max<a)
            max=a;

    }

    printf("%d %d %ld\n",min,max,sum);
    return 0;
}



Measured memory_bytes: 2104
#include<iostream>
using namespace std;
int main()
{
    int id , gate , i;
    int x , y;
    int x_max , y_min;
    cin >> id >> gate;
    x_max = 1;
    y_min = id;
    for( i=0 ; i < gate ; i++){
      cin >> x >> y;
      if( x_max < x )x_max = x;
      if( y_min > y )y_min = y;
    }
    if( y_min - x_max +1 <=0 ){
      y_min=0;
      x_max=1;
    }
    cout << y_min - x_max +1  << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
int n,mx;
string s[maxn];
map<string,int> m;
map<string,int> vis;
vector<string> v;
int read() {
	char ch = getchar();
	int x = 0, f = 1;
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9') x = x*10 + ch - 48, ch = getchar();
	return x * f;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>s[i];
		m[s[i]]++;
		mx=max(mx,m[s[i]]);
	}
	for(int i=1; i<=n; i++)
		if(m[s[i]]==mx&&!vis[s[i]])
			v.push_back(s[i]),vis[s[i]]=1;
	sort(v.begin(),v.end());
	for(int i=0; i<v.size(); i++)
		cout<<v[i]<<endl;
	return 0;
}

Measured memory_bytes: 40560
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define uniq(x) (x).erase(unique(all(x)),(x).end())

typedef long long ll;

const int INF = 1 << 29;

void solve(void){
    int N;
    cin >> N;
    vector <string> ss;
    int ns[3] = {INF};
    rep(N, i) {
        string s; cin >> s;
        ss.pb(s);
    }
    rep(N-1, i) Rep(i+1, N-1, j) {
        int a[2] = {stoi(ss[i]+ss[j]), stoi(ss[j]+ss[i])};
        rep(2, j) rep(3, i) {
            if (ns[i] > a[j]){
                Repr(1, i, k) ns[k+1] = ns[k]; 
                ns[i] = a[j];
                break;
            }
        }
    }
    printf("%d\n", ns[2]);
}

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



Measured memory_bytes: 3400
def canMonth(value):
    return 1 <= value and value <= 12


S = input()

F = int(S[:2])
B = int(S[2:])
fm = canMonth(F)
bm = canMonth(B)

if fm and bm:
    print('AMBIGUOUS')
elif not fm and not bm:
    print('NA')
elif fm:
    print('MMYY')
else:
    print('YYMM')


Measured memory_bytes: 3060
using System;

class StoneMonument{
    static void Main(string[] args){
        var ab = Console.ReadLine().Split(' ');
        var a = int.Parse(ab[0]);
        var b = int.Parse(ab[1]);

        var sub = b-a;

        var result = 0;
        for(int i=0; i<sub; i++){
            result = result + i;
        }
        result = result - a;

        Console.WriteLine(result);
    }
}

Measured memory_bytes: 11092
#include<stdio.h>
int main(){
  int a,b,c,d,sum,x,y;
  x=0;
  scanf("%d %d %d %d",&a,&b,&c,&d);
  sum=a+b+c+d;
  while(0<=x && x<=59){
    if(0<=sum && sum<=59){break;}
   if((sum-59)>0){
     sum=sum-60;
     x++;
    }
  }
  y=sum;
  printf("%d\n%d\n",x,y);
  return 0;
}

Measured memory_bytes: 0
//2019/3/14
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String S = sc.next();

		String T = sc.next();

		String SS = S+S;

		boolean flag = false;

		boolean ans = false;

		//はじめの文字
		for(int i=0;i<S.length();i++) {

			flag = false;

			for(int j=0;j<S.length();j++) {

				if(SS.charAt(i+j)!=T.charAt(j)) flag = true;
			}

			if(!flag) ans = true;
		}

		if(ans)System.out.println("Yes");

		else System.out.println("No");
	}

}


Measured memory_bytes: 25300
M, D = map(int, input().split())

count = 0
for m in range(1, M + 1):
    for d in range(2, D + 1):
        d1 = d % 10
        d10 = d // 10
        if not (2 <= d1 and 2 <= d10):
            continue
        if d1 * d10 == m:
            count += 1
print(count)


Measured memory_bytes: 39024
#include<bits/stdc++.h>
#define endl "\n" 
using namespace std;
#define debug(x) cout<<"The value of "<<#x<<" is "<<x<<endl;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    cin.sync_with_stdio(0); cin.tie(0); 
    int k,n;
    cin>>k>>n;
    vector<int>arr(n);
    for(auto& i:arr)
    cin>>i;
    vector<int>dis;
    for(int i=0;i<n-1;i++)
    dis.push_back(arr[i+1]-arr[i]);
    dis.push_back(arr[0]+(k-arr.back()));
    //take n-1 elements 
    //how??
    int sum=0;
    for(auto i:dis)
    sum+=i;
    int ans=k;
    for(int i=0;i<(int)dis.size();i++)
    ans=min(ans,sum-dis[i]);
    cout<<ans<<endl;
}


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

int main() {
    int n;cin>>n;
    ll ans=0;
    for (int i=1;i<=n;i++) {
        ll d=n/i;
        ans+=d*(d+1)/2*i;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int main(){
	int n;
	string a,b;
	cin>>a>>b;
	for(int i=0;i<a.size();i++){
		cout<<a[i];
		if(i<b.size())cout<<b[i];
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
template<class T> using pq = priority_queue<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -MOD * MOD;
const long double pi = 3.141592653589793;
int main() { // 問題文はしっかり読め!!!
	string s, t;
	cin >> s >> t;
	int x = s.size(), y = t.size();
	VV dp(x + 1, V(y + 1, 0));
	rep(i, x) {
		rep(j, y) {
			if (s[i] == t[j]) chmax(dp[i + 1][j + 1], dp[i][j] + 1);
			else chmax(dp[i + 1][j + 1], max(dp[i + 1][j], dp[i][j + 1]));
		}
	}
	// cout << dp[x][y] << endl;
	string ans = "";
	// dp[x][y]から復元していく
	// s[x]==t[y]ならば,ans+=s[x-1],x-=1,y-=1
	// そうでないならば,dp[x][y - 1]のほうが長いならばy-=1,dp[x - 1][y]のほうが長いならばx-=1
	// 最後にreverse
	while(x > 0 && y > 0) {
		if (s[x - 1] == t[y - 1]) {
			ans += s[x - 1];
			x -= 1; y -= 1;
		}
		else {
			if (dp[x][y - 1] > dp[x - 1][y]) y -= 1;
			else x -= 1;
		}
	}
	reverse(all(ans));
	cout << ans << endl;
	return 0;
}

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

using namespace std;
typedef long long ll;
#define REP(i,n) for (ll i = 0; i < (n); ++i)

int main(){
    string s0;
    cin >> s0;
    ll k;
    cin >> k;

    string s = s0;
    ll count = 0;
    for(ll i = 1; i < s.size(); ++i){
        if(s.at(i - 1) == s.at(i)){
            count++;
            s.at(i) = '*';
        }
    }
    if(k == 1 || s.at(0) != s.back()){
        cout << k * count << endl;
        return 0;
    }

    string s2 = s0;
    s2.at(0) = '*';
    ll count2 = 1;
    for(ll i = 1; i < s2.size(); ++i){
        if(s2.at(i - 1) == s2.at(i)){
            count2++;
            s2.at(i) = '*';
        }
    }

    if(s2.back() == '*'){
        if(k % 2 == 0){
            cout << k / 2 * (count + count2) << endl;
        }else{
            cout << k / 2 * (count + count2) + count << endl;
        }
    }else{
        cout  << count + (k - 1) * count2 << endl;
    }

    return 0;
}


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

#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()

int main(){
    string n;
    cin >> n;
    rep(i,n.size()){
        if(n[i]=='7'){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

}


Measured memory_bytes: 3628
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
    int w, h;
    cin >> w >> h;

    ll p[w], q[h];
    for(int i = 0; i < w; i++) cin >> p[i];
    for(int i = 0; i < h; i++) cin >> q[i];

    sort(p, p + w);
    sort(q, q + h);

    ll ans = 0;
    int idw = 0, idh = 0;
    int n = w + 1;
    int m = h + 1;
    while(idw != w || idh != h){
        if(idw == w){
            ans += q[idh] * n;
            m--;
            idh++;
        }
        else if(idh == h){
            ans += p[idw] * m;
            n--;
            idw++;
        }
        else if(p[idw] < q[idh]){
            ans += p[idw] * m;
            n--;
            idw++;
        }
        else {
            ans += q[idh] * n;
            m--;
            idh++;
        }
    }

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

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

int m,n,q;
vector<int> a,b,c,d;
int ans=0;

void dfs(vector<int> v){
  if(v.size()==n){
    int tmp=0;
    for(int i=0;i<q;i++){
      if(v[b[i]]-v[a[i]]==c[i]) tmp+=d[i];
    }
    ans=max(ans,tmp);
    return;
  }
  v.push_back(v.back());
  while(v.back()<=m){
    dfs(v);
    v.back()++;
  }
  return;
}

int main(){
  cin>>n>>m>>q;
  a=b=c=d=vector<int>(q);
  for(int i=0;i<q;i++){
    cin>>a[i]>>b[i]>>c[i]>>d[i];
    a[i]--;
    b[i]--;
  }
  dfs(vector<int>(1,1));
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3636
import collections

def test():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = collections.Counter(a).most_common()
    ans = 0; i = -1
    c = len(b)
    while k < c:
        ans = ans + b[i][1]
        c = c - 1
        i = i - 1
    print(ans)


if __name__ == "__main__":
    test()


Measured memory_bytes: 39320
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int n, a[100], b[101], vprev = 0, f, sm[101], vnext;
	double x = 0, t1, t2, vmax, y, z;
	cin >> n;
	
	for (int i = 0; i < n; i++)
		cin >> a[i];
	
	for (int i = 0; i < n; i++)
		cin >> b[i];
		
	if (n == 1)
	{
		if (2 * b[0] >= a[0])
			x += 0.25*a[0]*a[0];
		else
			x += 1.0*b[0]*b[0]+1.0*b[0]*(a[0]-2*b[0]);
	
	
		cout << setprecision(4) << fixed << x;
		return 0;
	}
	
	sm[n] = 0;
	
	for (int i = n-1; i >= 0; i--)
		sm[i] = sm[i+1]+a[i];
	
	b[n] = 0;
	
	for (int i = 0; i < n; i++)
	{
		vnext = min(b[i+1], min(b[i], vprev+a[i]));
		
		for (int j = i+2; j <= n; j++)
			vnext = min(vnext, sm[i+1]-sm[j]+b[j]);
			
		if (b[i]-vprev+b[i]-vnext <= a[i])
		{
		    y = 1.0*vprev*(b[i]-vprev)+1.0*b[i]*(b[i]-vnext)+0.5*(b[i]-vprev)*(b[i]-vprev)-0.5*(b[i]-vnext)*(b[i]-vnext)+1.0*b[i]*(a[i]-2*b[i]+vprev+vnext);
		   
			x += 1.0*vprev*(b[i]-vprev)+1.0*b[i]*(b[i]-vnext)+0.5*(b[i]-vprev)*(b[i]-vprev)-0.5*(b[i]-vnext)*(b[i]-vnext)+1.0*b[i]*(a[i]-2*b[i]+vprev+vnext);
			vprev = vnext;
			continue;
		}
		
		z = 0.5*(vprev+vnext+a[i]);
		x += vprev*(z-vprev)+0.5*(z-vprev)*(z-vprev)+1.0*z*(a[i]-z+vprev)-0.5*(a[i]-z+vprev)*(a[i]-z+vprev);
		
		vprev = vnext;
	}
	
	cout << setprecision(4) << fixed << x;
}

Measured memory_bytes: 256
import sys
from random import randint
from datetime import datetime

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]

def randomize(n):
    return [ randint(1, 26) for _ in range(n) ]

def get_now():
    dt = datetime.now()
    return dt.second + dt.microsecond/1000000

def main():
    start = get_now()
    end = get_now()
    # 開催日数
    D = ii()
    # 満足度の下がりやすさ
    C = lmi()
    # 得られる満足度
    S = lmif(D)
    # 最後に開かれた日付
    last = [0]*26
    # 開催するコンテスト
    T = randomize(D)

    def scoring():
        score = 0
        for i in range(D):
            score += S[i][T[i]-1]
            for j in range(26):
                score -= C[j] * (i - last[j])
        return score

    max_score = 0
    ans = T.copy()
    while end - start < 1.9:
        T = randomize(D)
        score = scoring()
        if max_score < score:
            ans = T.copy()
        # print(*T, score)
        end = get_now()
    print(*ans, sep='\n')

main()


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

#define gc getchar()
inline int read(){
	int x=0;int f=0;char c=gc;
	for(;c<48||c>57;c=gc)
		if(c=='-')f=1;
	for(;c>47&&c<58;c=gc)
		x=x*10+c-48;
	return f?-x:x;
}
#define io read()

#define maxn 500005
int n,a[maxn];

inline void init(){
	n=io;
	for(int i=1;i<=n;++i)a[i]=io;
}

struct data{
	int r,v;
}st[maxn];int top;

inline int check(int m){
	st[0]=(data){0,0};
	st[top=1]=(data){a[1],1};
	for(int i=2;i<=n;++i){
		if(a[i]>a[i-1]){
			st[++top]=(data){a[i],1};
			continue;
		}
		while(top&&st[top-1].r>=a[i])--top;
		
		if(st[top].v<m){
			if(st[top-1].r+1==a[i]){
				st[top].r=a[i];
				st[top].v++;
			}else{
				st[top].r=a[i]-1;
				st[top+1]=(data){a[i],st[top].v+1};
				++top;
			}
			continue;
		}
		
		while(top&&st[top].v==m)--top;
		if(!top)return 0;
		if(st[top-1].r+1==st[top].r)++st[top].v;
		else{
			st[top+1]=(data){st[top].r,st[top].v+1};
			st[top].r--;
			++top;
		}
		st[++top]=(data){a[i],1};
	}
	return 1;
}

inline void solve(){
	int l=1,r=n,mid,ans=1;
	while(l<=r){
		mid=l+r>>1;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans);
}

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

Measured memory_bytes: 4480
import numpy as np
c0= list(map(int, input().split(' ')))
c1= list(map(int, input().split(' ')))
c2= list(map(int, input().split(' ')))
 
C = np.array([c0, c1, c2])
if C[1][0] - C[0][0] == C[1][1]-C[0][1] == C[1][2] - C[0][2] and C[2][0] - C[0][0] == C[2][1]-C[0][1 ]== C[2][2] - C[0][2]  :
 print('Yes')
else:
 print('No')


Measured memory_bytes: 12492