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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
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; }
typedef long long ll;

const long long INF = 1LL << 60;

int main()
{
    int A, B, T;
    cin >> A >> B >> T;

    cout << (T / A) * B << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
typedef long long int lli;
#define tc int t;cin>>t;while(t--)
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vll vector<lli>


int main() {
   int n,x,y;
   cin>>n>>x>>y;
   int ans[n]={0};
   for(int i=1;i<=n;i++)
   {
       for(int j=i+1;j<=n;j++)
       {
             int dis1=max(x,i)-min(x,i)+1+max(y,j)-min(y,j);
             int dis2=max(x,j)-min(x,j)+1+max(y,i)-min(y,i);
             int dis3=j-i;
             int an=min(min(dis1,dis2),dis3);
             ans[an]++;
       }
   }
   for(int i=1;i<n;i++)
    cout<<ans[i]<<"\n";
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define sws ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INFINITO 1000000000
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define fo(i, n) for( int i = 0; i < n; i++ )


int main() {

    string s, t;
    cin >> s >> t;

    for ( size_t i = 0; i < s.size(); i++ ) {
        s = s.back() + s.substr(0, (int) s.size() - 1);
        // cout << s << endl;
        if ( s == t ) {
            cout << "Yes\n";
            return 0;
        }
    }
    if ( s != t ) cout << "No\n";
    else cout << "Yes\n";

    return 0;
}

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

using namespace std;

int main()
{
  int n, i, ans = 0, k = 0;
  string s;
  
  cin >> n >> s;

  for(i = 0; i < n; i++){
    if(s[i] == 'I'){
      k++;
      if(k > ans)ans = k;
    }
    else{
      k--;
    }
  }
  
  cout << ans << endl;
}

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

typedef long long ll;

int main() {
    int N; cin >> N;
    ll K; cin >> K;
    vector<ll> As(N);
    vector<ll> Fs(N);
    for (int i = 0; i < N; i++) {
        cin >> As[i];
    }
    sort(As.begin(), As.end());
    for (int i = 0; i < N; i++) {
        cin >> Fs[i];
    }
    sort(Fs.begin(), Fs.end(), greater<int>());
    ll bl = -1; ll br = 1e13; ll bm = (br + bl) / 2;
    while (br - bl > 1) {
        ll tempk = 0;
        for (int i = 0; i < N; i++) {
            if (Fs[i] * As[i] > bm) {
                tempk += (As[i] - (bm / Fs[i]));
            }
        }
        if (K >= tempk) {
            br = bm;
        } else {
            bl = bm;
        }
        bm = (bl + br) / 2;
    }
    cout << br << endl;
}

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

int getmd(int a,int b,int c,int d){
    return abs(a-c)+abs(b-d);
}

int main(){
    char a;
    cin >> a;

    if(a=='A')  puts("T");
    if(a=='T')  puts("A");
    if(a=='C')  puts("G");
    if(a=='G')  puts("C");

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <queue>
#include <stack>
#include <bitset>
#include <set>
#include <chrono>
#include <string>
#include <assert.h>

using namespace std;

#define endl '\n'


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

    int n;

    cin >> n;

    vector<pair<int,int>> a(n + 1);

    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }

    a[n] = {-1000000001, 2000000002};

    sort(a.begin(), a.end());

    vector<vector<int>> adj(n + 1);
    vector<int> dp(n + 1, 1);

    vector<int> stk;

    for (int i = n; i >= 0; --i) {
        int to = a[i].first + a[i].second;

        while (!stk.empty() && a[stk.back()].first < to) {
            adj[i].push_back(stk.back());
            stk.pop_back();
        }

        stk.push_back(i);

        for (auto x : adj[i]) {
            dp[i] = 1LL * dp[i] * (dp[x] + 1) % 998244353;
        }

        // cout << dp[i] << endl;
    }

    cout << dp[0] << endl;

    return 0;
}

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

namespace MyProgram
{
    public class Program
    {	
        public static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string ss = "";
            
            for(int i = 0 ; i < s.Length ; i++)
            {
                if((i+1) % 2 == 1)
                {
                    ss += s[i];
                }
            }
            Console.WriteLine(ss);
        }
    }
}

Measured memory_bytes: 34772
#include <iostream>
using namespace std;
int main(){
	int a,b;

	while(1){
		cin >> a >> b;
		if ( a == 0 && b == 0 ) break;

		if ( a < b ){
			cout << a << " " << b << endl;
		} else {
			cout << b << " " << a << endl; 
		}
	}
    return 0;
}
	

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define range(i, l, r) for(int i=l;i<r;i++)
using namespace std;
int main(int argc, char const *argv[]) {
  long long N, M;
  long long summ=0;
  std::cin >> N >> M;
  std::vector<std::vector<long long> > AB(N, std::vector<long long>(2));
  range(i, 0, N){
    std::cin >> AB[i][0] >> AB[i][1];
  }
  std::sort(AB.begin(), AB.end());
  range(i, 0, N){
    if(AB[i][1] < M){
      summ+=AB[i][0]*AB[i][1];
      M-=AB[i][1];
    }else{
      summ+=AB[i][0]*M;
      break;
    }
  }
  std::cout << summ << '\n';

  return 0;
}

Measured memory_bytes: 5760
#include<iostream>
#include<cstring>
using namespace std;
int dp[110];
int s;
bool flag;
long long int ans;
int solve(int i);
int main(){
  while(1){
    cin >> s;
    memset(dp, 0, sizeof(dp));
    flag = 0;
    if(s == 0) break;
    ans = solve(0);
    ans /= 10;
    if(!ans) flag = 1;
    if(ans % 365) flag = 1;
    ans /= 365;
    if(flag == 1) ans++;
    cout << ans << endl;
  }
}

int solve(int i){
  if(i == s) return 1;
  if(i > s) return 0;
  if(dp[i] > 0) return dp[i];
  return dp[i] = solve(i + 1) + solve(i + 2) + solve(i + 3);
}

Measured memory_bytes: 1156
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {

    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long ans = 0;
        int N = sc.nextInt();
        int M = sc.nextInt();
        System.out.println((N==M)?"Yes":"No");
    }
}


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

int main(){
  int a,b;
  std::cin >> a>>b;
  std::cout << a*b << '\n';


  return 0;
}


Measured memory_bytes: 3636
s=input()
ans=0
acgt="ACGT"
for i in range(0,len(s)):
  for j in range(i+1,len(s)+1):
    x=s[i:j]
    z=sum([ y in acgt for y in x])
    if z==j-i:
      ans=max(ans,z)
      
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool is_palindrome(string str){
  string rstr = str;
  reverse(str.begin(), str.end());

  return rstr == str;
}

int main(){
  string s;
  cin >> s;

  if (s.find('x') == string::npos){
    if (is_palindrome(s)) printf("0\n");
    else printf("-1\n");
  }else{
    string copys = s;
    copys.erase(remove(copys.begin(), copys.end(), 'x'), copys.end());
    if(is_palindrome(copys)){
      int m = copys.size(), ans = 0;
      int head = 0, tail = s.size() - 1;
      while(head < tail){
        if(s[head] != s[tail]){
          if(s[head]=='x') head++;
          else tail--;
          ans++;
        }else{
          head++;
          tail--;
        }
      }
      printf("%d\n", ans);
      
    }else{
      printf("-1\n");
    }
  }
}


Measured memory_bytes: 3896
N=int(input())
p=list(map(float,input().split()))
dp=[0]*(N+1)
dp[0]=1
for i in range(0,N):
    for j in range(i+1,-1,-1):
        if(j!=0):
            dp[j]=dp[j-1]*p[i] + dp[j]*(1-p[i])
        else:
            dp[j]=dp[j]*(1-p[i])
ans=0
# print(dp)
for i in range(N//2+1,N+1):
    ans+=dp[i]
print(ans)

Measured memory_bytes: 75720
#include <bits/stdc++.h>
#define int long long
#define boost() ios_base :: sync_with_stdio(0); cin.tie(); cout.tie(); cout << fixed; cout << setprecision(15); srand(time(NULL))
#define all(x) x.begin(), x.end()
using namespace std;

int n;
int h[33];

signed main () {
  cin >> n;
  int cur = 0, res = 0;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
    if (h[i] >= cur) res += 1;
    cur = max (h[i], cur);
  }
  cout << res << endl;
  return 0;
}



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

using namespace std;

const long long MOD=1e9+7;

int n,a,b;

int getMinBig(int num, int turns){
    int high=turns;
    int low=0;
    for(int i=0; i<30;i++){
        long long mid=(low+high)/2;
        if(mid*a+(turns-mid)*b>= num){
            high=mid;
        }
        else{
            low=mid;
        }
        
    }
    return high;
}

bool isDone(int turns, vector<int>& vi){
    int tc=0;
    for(int i:vi){
        if(i>(long long)turns*a) return false;
        tc+=getMinBig(i,turns);
        if(tc>turns) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    
    
    
    cin>>n>>a>>b;
    vector<int> vi(n);
    for(int i=0; i<n; i++){
        cin>>vi[i];
    }
    
    int lo=0, high=1000000001;
    for(int i=0; i<50; i++){
        int mid=(lo+high)/2;
        if(isDone(mid,vi)){
            high=mid;
        }
        else{
            lo=mid;
        }
    }
    cout<<high<<endl;
    
    //cout<<getMinBig(4,2);
    //cout<<ans<<endl;
    
    
    
    
    return 0;
}


Measured memory_bytes: 640
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

#[allow(dead_code)]
fn with_stdout_lock<F: FnOnce(std::io::BufWriter<std::io::StdoutLock>)>(f: F) {
    let out = std::io::stdout();
    let w = std::io::BufWriter::new(out.lock());
    f(w);
}

fn main() {
    let n: usize = input();
    let a: Vec<i32> = (0..n).map(|_| input()).collect();

    let ans = a.iter().fold(a[0], |acc, &a| gcd(acc, a));
    println!("{}", ans);
}

fn gcd(x: i32, y: i32) -> i32 {
    if y == 0 {
        x
    } else {
        gcd(y, x % y)
    }
}


Measured memory_bytes: 4352
import numpy as np
H, W = map(int, input().split())
grid = np.array([list(input()) for _ in range(H)], dtype="U1")

row = []
col = []
for i in range(H):
    if (grid[i] != ".").any():
        row.append(i)

trans_grid = np.transpose(grid)
for i in range(W):
    if (trans_grid[i] != ".").any():
        col.append(i)


G = grid[row][:, col]
for g in G:
    print("".join(g))

Measured memory_bytes: 14460
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
int seq[1000005] = { 0 }, res = 0;
int main() {
	cin >> s;
	seq[0] = 1;
	for (int i = 1; i < s.size(); i++) {
		if (s[i] == s[i - 1]) seq[i] = seq[i - 1] + 1;
		else seq[i] = 1;
	}
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'O'&&s[i+1]=='I') {
			int k = seq[i];
			if (s[i+k]=='I'&&seq[i + k] == k&&seq[i-k]>=k&&s[i-k]=='J') {
				res = max(res, k);
			}
		}
	}
	cout << res << endl;
	return 0;
}


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

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 100007;

int n;
multiset < int > e[MAXN];
int deg[MAXN];
PII q[MAXN];
int fa[MAXN];

void init ();
void input ();
void work ();

int getfa ( int now )
{
	return fa[now] ? getfa ( fa[now] ) : now;
}



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method
	
	scanf ( "%d", &n );
	int u, v;
	lp ( i, 0, 2 * n - 2 ){
		scanf ( "%d%d", &u, &v );
		e[u].insert ( v ), e[v].insert ( u );
	}
}

void work ()
{
	// main work
	
	int l = 0, r = 0;
	
	lpi ( i, 1, n ){
		for ( auto x : e[i] ){
			if ( i < x && ( l == r || ( q[r-1] != MP ( i, x ) ) ) && e[i].count ( x ) == 2 ) q[r++] = MP ( i, x );
		}
	}
	
	lp ( i, l, r ) e[q[i].first].erase ( q[i].second ), e[q[i].second].erase ( q[i].first );
	
	lpi ( i, 1, n ) deg[i] = 1;
	
	int tr = r;
	
	int nu, nv;
	while ( l < r ){
//		if ( l == tr ) cerr << "----------------------" << endl;
//		cerr << q[l].first << " " << q[l].second << " ";
		nu = getfa ( q[l].first ), nv = getfa ( q[l].second ), ++l;
//		cerr << nu << " " << nv << endl;
		
		if ( deg[nu] < deg[nv] ) swap ( nu, nv );
		fa[nv] = nu;
		
		for ( auto x : e[nv] ){
			x = getfa ( x );
			if ( x ^ nu ){
				if ( e[nu].find ( x ) != e[nu].end () ) q[r++] = MP ( qmin ( nu, x ), qmax ( nu, x ) ), e[nu].erase ( x ), e[x].erase ( nu );
				else e[nu].insert ( x ), e[x].insert ( nu );
				e[x].erase ( e[x].find ( nv ) );
			}
		}
		e[nv].clear ();
		e[nu].erase ( nv );
		
		deg[nu] += deg[nv];
	}
	
	printf ( ( r == n - 1 ) ? "YES\n" : "NO\n" );
}

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

// input
string s;


void input() {
    cin >> s;
}


int main() {
    input();
    s[5] = s[13] = ' ';
    cout << s << endl;
}


Measured memory_bytes: 3604
#pragma GCC target ("avx2")
#pragma GCC optimize "trapv"
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define input(a,n) for(ll i1=0;i1<n;i1++)cin>>a[i1]
#define ll long long
#define pi 2 * acos(0.0)
#define usll unordered_set<ll>
#define sll set<ll>
#define vll vector<ll>
#define mll map<ll,ll>
#define pll pair<ll,ll>
#define umll unordered_map<ll,ll>
#define S second
#define sz size()
#define all(v) v.begin(),v.end()
#define Y cout<< "YES"<< "\n"
#define N cout<< "NO"<< "\n"
#define F first
#define mp make_pair
#define pb push_back
#define pf push_front
#define ld long double
#define mod 1000000007
using namespace std;
unsigned long long power(long long x,
                         ll y, ll p)
{
    long long res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}

// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n, int p)
{
    return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
unsigned long long ncr(long long n,
                                 ll r, ll p)
{
    // Base case
    if (r == 0)
        return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    long long fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll s;
    cin>>s;
    ll p=s/3,ans=0;
    for(ll i=1;i<=p;i++)
    {
        ans=((ans%mod)+(ncr(s-3*i+i-1,i-1,mod)))%mod;
    }
    cout<<ans;
    return 0;
}


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


int main(){
	
	char s; cin >> s;
	
	if(s=='a' or s=='i' or s=='u' or s=='e' or s=='o') cout << "vowel" << endl;
	else cout << "consonant" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define X first
#define Y second

typedef pair<int,int> coord;

class t_res{
	public:
	bool flag;
	int x;
	int y;
};
vector<coord> want;
set<coord> all;


t_res find(int x,int y){
	coord check;
	t_res ret;
	int xx = x-want[0].X;
	int yy = y-want[0].Y;
	//cout << xx << " "  << yy << endl;
	rep(i,want.size()){
		check.X = want[i].X + xx;
		check.Y = want[i].Y + yy;
		if(all.find(check) == all.end() ){
			ret.flag = false;
			return ret;
		}
	}
	ret.flag = true;
	ret.x = xx;
	ret.y = yy;
	return ret;
}
int main(){
	int n,m;
	pair<int,int> inp,t;
	t_res get;
	while(cin >> n,n){
		want.resize(n);
		all.clear();
		rep(i,n){
			cin >> want[i].X >> want[i].Y;
		}
		cin >> m;
		rep(i,m){
			cin >> inp.X >> inp.Y;
			all.insert(make_pair(inp.X,inp.Y));
		}
		set<coord>::iterator it = all.begin();
		while( it != all.end() ){
			t = (*it);
			get = find(t.X,t.Y);
			if(get.flag){
				cout << get.x << " " << get.y << endl;
			}
			++it;
		}
	}
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
using namespace std;
const int INF = 1e9;
typedef long long ll;

int main(){
  int n,q;
  cin >> n >> q;
  vector <int> res;
  int a[n];
  int sq = sqrt(n);
  int nsq = n/sq+1;
  int lazy[nsq];
  fill(a,a+n,2147483647);
  fill(lazy,lazy+nsq,-1);
  REP(i,q){
    int z;
    cin >> z;
    if(z == 0){
      int s,t,x;
      cin >> s >> t >> x;

      /*if(s == t){
	a[s] = x;
	}*/
      if(t/sq == s/sq){
	if(lazy[t/sq] >= 0){
	  fill_n(a+(t/sq)*sq,sq,lazy[t/sq]);
	  lazy[t/sq] = -1;
	}
	if(t-s+1 == sq){
	  lazy[t/sq] = x;
	}
	else{
	  fill_n(a+s,t-s+1,x);
	}
	//cout << "debug1" <<endl;
      }

      else{
	//cout << "debug3" << endl;
	int f = s,to = t;
	while(to%sq != (sq - 1)){
	  to--;
	}
	while(f%sq != 0){
	  f++;
	}
	if(lazy[t/sq] >= 0){
	  fill_n(a+(t/sq)*sq,sq,lazy[t/sq]);
	}
	if(lazy[s/sq] >= 0){
	  fill_n(a+(s/sq)*sq,sq,lazy[s/sq]);
	}
	fill_n(a+to+1,t-to,x);
	lazy[t/sq] = -1;
	fill_n(a+s,f-s,x);
	lazy[s/sq] = -1;
	f = f/sq;
	to = to/sq;
	if(f <= to){
	  fill_n(lazy+f,to-f+1,x);
	}
	
      }
      /*REP(i,n)
	cout << a[i] << "  ";
	cout << endl;*/
    }
    else{
      int x;
      cin >> x;
      int te = x / sq;
      
      if(lazy[te] < 0){
	//cout << a[x] << endl;
	res.pb(a[x]);
      }
      else{
	fill_n(a+te*sq,sq,lazy[te]);
	lazy[te] = -1;
	//cout << a[x] << endl;
	res.pb(a[x]);

      }
      
    }
    
  }
  for(int i = 0;i < res.size();i++){
    cout << res[i] << endl;
  }
  //cout << res.size() << endl;
  return 0;
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define faster ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define ld long double
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i,a,b) for(ll i = a; i < b; i++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b) / gcd(a, b)
#define bins(v, x) binary_search(v.begin(), v.end(), x)
const double pi = 2*acos(0.0);
const int INF = 1e9+1;
const int mod = 1e9+7;
const int mod1 = 998244353;
 
ll modExp(ll base, ll exp, ll mod) {
   ll res = 1;
   while (exp > 0) {
    	if (exp % 2 == 1) {
        	res= (res * base) % mod;
		}
      exp = exp >> 1;
      base = (base * base) % mod;
   }
   return res;
}

ll inverse(ll base, ll exp, ll mod) {
   return modExp(base, exp - 2, mod);
}

bool compare(const pair<int, int>&i, const pair<int, int>&j) {
    return (i.S > j.S || (i.S == j.S && i.F > j.F));
}

void test() {
   int n, k;
   cin >> n >> k;

   vi p(n);
   REP(i,0,n) cin >> p[i];

   sort(all(p));
   ll sum = 0;
   for(int i = 0; i < k; i++) {
      sum += p[i];
   }

   cout << sum;
}

int main() {
   //freopen("input.txt","r",stdin);
   //freopen("output.txt","w",stdout);
   faster;
   cout.precision(10);
   cout << fixed;

   int t = 1;
   //cin >> t;
   while(t--)
      test();

   return 0;
}

Measured memory_bytes: 3664
#include<stdio.h>
int main(){
  int a,b,c,d,min;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  if(a<b)
    min=a;
  else
    min=b;
  if(c<d)
    min+=c;
  else
    min+=d;
  printf("%d\n",min);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <numeric>

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

int main() {
	int N;
	int C[500],S[500],F[500];
	cin >> N;
	int i;
	int t = 0;
	int T[500];
	N--;
	if (N <= 0) {
		cout << 0;
		return 0;
	}
	rep(i, N) {
		cin >> C[i] >> S[i] >> F[i];
	}
	T[N - 1] = S[N - 1] + C[N - 1];
	for (i = N - 2; i >= 0; i--) {
		t = S[i] + C[i];
		int j;
		for ( j = i + 1; j < N; j++) {
			if (t <= S[j]) {
				T[i] = T[j];
				break;
			}
			t +=(t%F[j] ==0 ? 0 :F[j] - t % F[j]);
			t += C[j];
		}
		if (j == N) {
			T[i] = t;
		}

	

	}
	rep(i, N) {
		cout << T[i] << endl;
	}
	cout << 0 << endl;
	return 0;

}



Measured memory_bytes: 256
import           Control.Applicative
import           Control.Monad
import           Data.List
import           Text.Printf

import           System.Random

helpMod::Integer->Integer->Integer->Integer
helpMod a d n= fun a d where
    fun a 1 = mod a n
    fun a 2 = mod (a^2) n
    fun a d = let
            p=fun (mod (a^2) n) (div d 2)
            q=if odd d then mod (a*p) n else p
          in mod q n

isProbable::Integer-> Bool
isProbable n |n<=1 = False
         |n==2 = True
         |even n = False
         |otherwise = rabinMiller [2,3,5,7,11,13,17,19] n s d where
             d=until (\x->mod x 2/=0) (`div` 2) (n-1) --(n-1=2^s*d)
             s=until (\x->d*2^x==pred n) (+1) 0  --counts the power


rabinMiller::[Integer]->Integer->Integer->Integer-> Bool
rabinMiller [] _ _ _ = True
rabinMiller (a:xs) n s d =  if a == n then True
                 else  case x==1 of
                    True -> rabinMiller xs n s d
                    _ -> if any ( ==pred n) $ take (fromIntegral s) $ iterate (\e->mod (e^2) n)  x then rabinMiller xs n s d
                          else  False
                   where x=helpMod a d n

fn :: Integer -> Integer -> Integer -> Integer
fn x c n = mod ( x^2 + c ) n

pollard :: Integer -> IO  Integer
pollard n
  | even n = return  2
  | otherwise =
      randomRIO ( 2 , n - 1 ) >>=
     (\x' -> randomRIO ( 2 , n - 1 ) >>=
        (\c ->  return ( until ( \( _ , _ , d ) -> d /= 1 || d == n )  ( \( x , y , d ) -> ( fn x c n , fn ( fn y c n ) c n , gcd ( fn x c n - fn ( fn y c n ) c n  ) n ) )  ( x' , x' , 1 ) ) >>=
        ( \( _ , _ , k ) -> return k  ) ) )

factor :: Integer -> IO [ Integer ]
factor 1 = return []
factor n =
   (return . isProbable $ n ) >>=
    (\x -> case x of
        True -> return [n]
        _    -> pollard n >>=
              (\d -> case d of
                   1 -> factor n
                   _ -> factor d  >>= (\l -> ( factor.div n $ d ) >>= ( \m -> return $ l ++ m ) ) ) )

main = do
        line<-getLine
        let n=read line ::Integer
        m<- factor n
        putStrLn $ show n ++ ": "++ (unwords (map show (sort m)))
        return ()



Measured memory_bytes: 4556
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://apc001.contest.atcoder.jp/tasks/apc001_b>
問題文============================================================
 長さ N の数列 a1,a2,..,aN と b1,b2,..,bN が与えられます。
 以下の操作を 0 回以上好きなだけ繰り返して、数列 a と b を一致させられるか判定してください。
 
 操作： 1 以上 N 以下の整数 i,j (一致していてもよい)を選び、次の2つのことを同時に行う。
 
 ai に 2 を足す
 bj に 1 を足す

=================================================================

解説=============================================================

================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    vector<ll> a(N),b(N);
    for(auto&in:a) cin >> in;
    for(auto&in:b) cin >> in;
    ll Cnt = accumulate(b.begin(),b.end(),0LL) - accumulate(a.begin(), a.end(),0LL);
    for(int i = 0; i < N;i++){
        if(a[i] < b[i]){
            Cnt -= (b[i]-a[i]+1)/2;
        }
    }
    if(Cnt >= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
	return 0;
}


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


int main(){

    int N,M,k;
    cin >> N >> M;
    int p[10];
    vector<vector<int>> sw(M);
    for(int i=0;i<M;i++) {
        cin >> k;
        sw[i].resize(k);
        for(int j=0;j<k;j++) {
            cin >> sw[i][j];
            sw[i][j]--;
        }
    }
    for(int i=0;i<M;i++) cin >> p[i];
    int ans = 0;
    for(int i=0;i<(1<<N);i++){
        bool flag = true;
        for(int j=0;j<M;j++) {
            int cnt = 0;
            for(int x : sw[j]){
                if(i>>x & 1) cnt++;
            }
            cnt %= 2;
            if(cnt != p[j]) flag = false;
        }
        if(flag) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

cdef extern from "/opt/atcoder-stl/atcoder/math.hpp" namespace "atcoder":
    cdef long long floor_sum(long long n, long long m, long long a, long long b)

from libc.stdio cimport scanf, printf
cdef int t, i
cdef long long n, m, a, b
scanf('%d', &t)
for i in range(t):
    scanf('%lld%lld%lld%lld', &n, &m, &a, &b)
    printf('%lld\n', floor_sum(n, m, a, b))
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Measured memory_bytes: 9052
s = input()
n = int(input())
rev = 0
rev_check = False
first = list()
last = list()
for i in range(n):
    q = list(input().split())
    if q[0] == "1":
        rev += 1
        rev_check = not rev_check
    else:
        if rev_check ==  True:
            if q[1] == "1":
                last.append(q[2])
            else:
                first.append(q[2])
        else:
            if q[1] == "1":
                first.append(q[2])
            else:
                last.append(q[2])
if rev_check == False:
    print("".join(reversed(first)) + s + "".join(last))
else:
    print("".join(reversed(last)) + s[::-1] + "".join(first))


Measured memory_bytes: 6252
#include<stdio.h>
#include<string.h>

int main() {
	char s[200];
	char p[100];

	scanf("%s", s);
	scanf("%s", p);
	
	sprintf(s, "%s%s", s, s);

	if (strstr(s, p) != NULL) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 560
#include<stdio.h>
int main(void)
{
	int a[10+1],b[10+1],c[10+1],ten[10+1],i,j,n,max,cnt;
	char moziretsu[10+1][20+1];
	cnt=0;
	scanf("%d",&n);
	while(n!=0) {
		if(0<cnt) {
			printf("\n");
		}
		for(i=0;i<n;i++) {
			scanf("%s %d %d %d",moziretsu[i],&a[i],&b[i],&c[i]);
			ten[i]=a[i]*3+b[i]*0+c[i]*1;
		}
		for(j=0;j<n;j++) {
			max=-1;
			for(i=0;i<n;i++) {
				if(max<ten[i]) {
					max=ten[i];
				}
			}
			for(i=0;i<n;i++) {
				if(max==ten[i]) {
					printf("%s,%d\n",moziretsu[i],ten[i]);
					ten[i]=-2;
				}
			}
		}
		cnt++;
	scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 604
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main() 
{
	ll n=0;
	ll ans=0;
	cin>>n;
	vector<string> s(n);
	map<string,int> b; 
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
		b[s[i]]=1;

	}
	ans=b.size();
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 25148
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<bitset>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
typedef long long int ll;
typedef pair<int,int> P;
struct edge{int to,cost;};
#define REP(i,n) for(int i=0;i<(n);i++)
const int INF=100000000;

int main(){
	int n,a[110],count=1,ans=0;
	cin>>n;
	REP(i,n){
		cin>>a[i];
	}
	for(int i=0;i<n-1;i++){
		if(a[i]==a[i+1]){
			count++;
		}
		DEB(count)END
		if(a[i]!=a[i+1]){
			ans+=count/2;
			count=1;
		}
	}
	ans+=count/2;
	cout<<ans<<endl;
	return 0;
}

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


def m():

    def is_match(x, y):
        for i in range(M):
            for j in range(M):
                if A[x+i][y+j] == B[i][j]:
                    pass
                else:
                    return False
        return True

    for x in range(N-M+1):
        for y in range(N-M+1):
            if is_match(x, y):
                return 'Yes'
            else:
                continue
    return 'No'


print(m())


Measured memory_bytes: 3064
A=list(input())
n=len(A)
ind=[[] for i in range(26)]
for i in range(n):
    ind[ord(A[i])-97].append(i)
cnt=0
for i in range(26):
    cnt+=len(ind[i])*(len(ind[i])-1)//2

print(n*(n-1)//2-cnt+1)

Measured memory_bytes: 95820
import unittest


class TestC(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(2020, 2040), 2)

    def test_2(self):
        self.assertEqual(think(4, 5), 20)


def solve():
    l, r = read()
    result = think(l, r)
    write(result)


def read():
    return read_int(2)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(l, r):
    mode = 2019
    m = 2018

    for i in range(l, r):
        for j in range(i + 1, r + 1):
            if i % mode == 0 or j % mode == 0:
                return 0
            m = min(m, (i % mode * j % mode) % mode)
    return m


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using u64 = uint_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;

void solve() {
    i64 n;
    cin >> n;

    vector<vector<i64>> dp(3, vector<i64>(n + 1));
    for (i64 i = 0; i < n; i++) {
        vector<i64> h(3);
        for (auto& e : h) cin >> e;
        for (i64 j = 0; j < 3; j++) {
            dp[j][i + 1] = max(dp[(j + 1) % 3][i] + h[(j + 1) % 3], dp[(j + 2) % 3][i] + h[(j + 2) % 3]);
        }
    }
    cout << max({ dp[0][n], dp[1][n], dp[2][n] }) << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 6372
import numpy as np

n, t = map(int, input().split())
dt = [list(map(int, input().split())) for _ in range(n)]
dt.sort()
dp = np.zeros(t, dtype=int)
ans = 0
for a, b in dt:
    ans = max(ans, dp[-1]+b)
    np.maximum(dp[a:], dp[:-a]+b, out=dp[a:])
print(ans)

Measured memory_bytes: 12772
#include<bits/stdc++.h>
#define mo 1000000007
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long n,k,i,j,jc[4000005],ny[4000005],f[2005];
long long ksm(long long u,long long v){
	long long o=1;
	while(v){
		if(v&1)
			o=o*u%mo;
		u=u*u%mo;
		v>>=1;
	}	
	return o;
}
long long C(long long u,long long v){
	return jc[u]*ny[v]%mo*ny[u-v]%mo;
}
int main(){
	n=read();k=read();
	if(k==1){
		pus(1,2);
		return 0;
	}
	jc[0]=1;
	for(i=1;i<=n*k;i++)
		jc[i]=jc[i-1]*i%mo;
	ny[n*k]=ksm(jc[n*k],mo-2);
	for(i=n*k-1;i>=0;i--)
		ny[i]=ny[i+1]*(i+1)%mo;
	f[0]=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)
			f[j]=(f[j]+f[j-1]*C(n*k-i-(j-1)*(k-1)-1,k-2))%mo;
	pus(f[n]*jc[n]%mo,2);
    return 0;
}

Measured memory_bytes: 62720
#include<stdio.h>
#include<math.h>
typedef struct {
    double x;
    double y;
}pin;

void koho(int n,pin p1,pin p2){
    pin s,t,u;
    double r=M_PI/3;
    if(n==0)return;
    s.x=(2*p1.x+p2.x)/3;
    s.y=(2*p1.y+p2.y)/3;
    t.x=(p1.x+2*p2.x)/3;
    t.y=(p1.y+2*p2.y)/3;
    u.x=(t.x-s.x)*cos(r)-(t.y-s.y)*sin(r)+s.x;
    u.y=(t.x-s.x)*sin(r)+(t.y-s.y)*cos(r)+s.y;

koho(n-1,p1,s);
printf("%f %f\n",s.x,s.y);
koho(n-1,s,u);
printf("%f %f\n",u.x,u.y);
koho(n-1,u,t);
printf("%f %f\n",t.x,t.y);
koho(n-1,t,p2);    
}

int main(){
    int n;
    pin p1={0,0},p2={100,0};
    scanf("%d",&n);
    printf("%f %f\n",p1.x,p1.y);
    koho(n,p1,p2);
    printf("%f %f\n",p2.x,p2.y);
    return 0;
}


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

a = []
for _ in range(n):
    X, L = map(int, input().split())
    a.append([X + L, X - L])

a.sort()

ans = 0
b = - float('inf')
for t, s in a:
    if s >= b:
        b = t
        ans += 1

print(ans)

Measured memory_bytes: 20104
#include <bits/stdc++.h>
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
#define _GLIBCXX_DEBUG

using ll = long long;
using ull = unsigned long long;
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 ll mod = 1e9+7;
void chmod(ll &M){
  if(M >= mod) M %= mod;
  else if(M < 0){
     M += (abs(M)/mod + 1)*mod;
    M %= mod;
}
}
ll modpow(ll x, ll n){
   if(n==0) return 1;
  ll res=modpow(x, n/2);
 if(n%2==0) return res*res%mod;
else return res*res%mod*x%mod;
}
int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };
long long GCD(long long a, long long b) {
  if (b == 0) return a;
  else return GCD(b, a % b);
}

using namespace std;
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
int main() 
{
    ll N, M;
    cin >> N >> M;
    ll sum = 0;
    rep(i, M) {
        int a;
        cin >> a;
        sum += a;
    }
    if(N - sum >= 0) cout << N - sum << "\n";
    else cout << -1 << "\n";
}


Measured memory_bytes: 3568
import sys
from collections import deque
s=sys.stdin.readlines()
_,q=map(int,s[0].split())
f=lambda x,y:(x,int(y))
d=deque(f(*e.split())for e in s[1:])
t=0
while d:
 k,v=d.popleft()
 if v>q:
  v-=q
  t+=q
  d.append([k,v])
 else:
  t+=v
  print(k,t)


Measured memory_bytes: 16296
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
#include <cmath>

using ll = long long;
using namespace std;
#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};


int main() {

    int n,b;
    cin >> n;

    int ans = 0;

    int b4 = 1000000;
    for (int i = 0; i < n-1; i++) {

        cin >> b;

        ans += min(b, b4);
        b4 = b;
    }

    cout << ans + b4 << endl;
}

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

int main(){
    std::vector<int> A(3);
    std::cin>>A[0]>>A[1]>>A[2];

    std::sort(A.begin(), A.end());
    std::cout<<A[2] - A[0]<<std::endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
S = sorted([int(a) for a in input().split()])
X = [1] + [0] * N

def popX(i0):
    for i in range(i0, N+1):
        if X[i]:
            X[i] -= 1
            return i
    return N+1
def addX():
    for l in L:
        for i in range(l+1, N+1):
            X[i] += 1

while S:
    a = S.pop()
    L = [popX(0)]
    while S and S[-1] == a:
        S.pop()
        L.append(popX(L[-1]))
    if L[-1] > N:
        print("No")
        break
    addX()
else:
    print("Yes")

Measured memory_bytes: 34676
import string
N = int(input())
C = list(input())
L = list(string.ascii_uppercase)
count = 0
for i in C:
    for j in L:
        if i == j:
            break
        count += 1
    if count + N <= 25:
        print(L[count+N], end='')
    else:
        print(L[count+N-26], end='')
    count = 0

Measured memory_bytes: 5112
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int kazu(int x) {
    int temp;
    if (1 <= x && x < 10) {
        return 1;
    }
    else if (100 <= x && x < 1000) {
        return 1;
    }
    else if (10000 <= x && x < 100000) {
        return 1;
    }
    else
    {
        return 0;
    }
}

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += kazu(i);
    }

    cout << ans;


    return 0;
}

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

template <typename T>
using Matrix = vector<vector<T>>;

template <typename T>
Matrix<T> matrix(const int R, const int C, const T x = T())
{
    return Matrix<T>(R, vector<T>(C, x));
}

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

    int R, C, Q; cin >> R >> C >> Q;

    auto grid = matrix<int>(R+2, C+2);
    for (auto r = 1; r <= R; r++)
    {
        string row; cin >> row;
        for (auto c = 1; c <= C; c++)
            grid[r][c] = row[c-1] == '1';
    }

    auto squares = matrix<int>(R+1, C+1);
    auto vertical = matrix<int>(R+1, C+1);
    auto horizontal = matrix<int>(R+1, C+1);
    for (auto r = 1; r <= R; r++)
        for (auto c = 1; c <= C; c++)
        {
            squares[r][c] = squares[r][c-1] + squares[r-1][c]
                            - squares[r-1][c-1]
                            + grid[r][c];
            vertical[r][c] = vertical[r][c-1] + vertical[r-1][c]
                             - vertical[r-1][c-1]
                             + (grid[r][c] == 1 && grid[r][c+1] == 1);
            horizontal[r][c] = horizontal[r][c-1] + horizontal[r-1][c]
                               - horizontal[r-1][c-1]
                               + (grid[r][c] == 1 && grid[r+1][c] == 1);
        }

    while (Q--)
    {
        int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;

        auto answer = squares[r2][c2]
                      - (squares[r2][c1-1] + squares[r1-1][c2])
                      + squares[r1-1][c1-1];
        answer -= vertical[r2][c2-1]
                  - (vertical[r2][c1-1] + vertical[r1-1][c2-1])
                  + vertical[r1-1][c1-1];
        answer -= horizontal[r2-1][c2]
                  - (horizontal[r1-1][c2] + horizontal[r2-1][c1-1])
                  + horizontal[r1-1][c1-1];
        cout << answer << "\n";
    }
}


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

#define all(A) begin(A), end(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;

bool check (char ch) {
  if (ch == 'A') return true;
  if (ch == 'C') return true;
  if (ch == 'G') return true;
  if (ch == 'T') return true;
  return false;
}

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  string s;
  cin >> s;
  int n = sz(s);
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      bool ok = true;
      for (int k = i; k <= j; k++) {
        ok &= check(s[k]);
      }
      if (ok) ans = max(ans, j - i + 1);
    }
  }
  cout << ans << endl;
  return (0);
}


Measured memory_bytes: 256
//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
string s,t;
int dp[3005][3005],from[3005][3005];

void print_LCS(int i,int j){
	if(i==0 || j==0)
		return;
	if(from[i][j] == 0){
		print_LCS(i-1,j-1);
		cout<<s[i-1];
	}
	else if(from[i][j] == 1)
		print_LCS(i-1,j);
	else
		print_LCS(i,j-1);
}

int main(){
	IOS
	while(cin>>s>>t){
		for(int i=0 ; i<3005 ; i++){
			dp[i][0] = dp[0][i] = 0;
		}
		for(int i=1 ; i<=s.size() ; i++){
			for(int j=1 ; j<=t.size() ; j++){
				if(s[i-1] == t[j-1]){
					dp[i][j] = dp[i-1][j-1]+1;
					from[i][j]=0;
				}
				else{
					if(dp[i-1][j] > dp[i][j-1])
						from[i][j]=1;
					else
						from[i][j]=2;
					dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		print_LCS(s.size(),t.size());
	}
	return 0;
}


Measured memory_bytes: 74128
h, w = map(int, input().split())
mod2 = lambda x: int(x) % 2
a = [list(map(mod2, input().split())) for _ in range(h)]

cnt, ans, rvs = 0, [], -1
for i, ai in enumerate(a):
    rvs *= -1
    for j in range(w)[::rvs]:
        if cnt == 1:
            ans.append([bi + 1, bj + 1, i + 1, j + 1])
            ai[j] += 1
        cnt = int(ai[j] == 1)
        bi, bj = i, j

print(len(ans))
for q in ans:
    print(*q)


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

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

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

  int W, H, w, h, x, y;
  cin >> W >> H >> w >> h >> x >> y;

  // 穴の四隅を求める
  int x1 = x - w/2, y1 = y - h/2;
  int x4 = x + w/2, y4 = y + h/2;

  // cout << x1 << " " << y1 << endl << x4 << " " << y4 << endl;

  chmin(x1, W/2);  chmin(x4, W/2); 
  chmax(x1, -W/2); chmax(x4, -W/2);
  chmin(y1, H/2);  chmin(y4, H/2);
  chmax(y1, -H/2); chmax(y4, -H/2);

  // cout << x1 << " " << y1 << endl << x4 << " " << y4 << endl;
  double cx = (x1+x4)/2.0, cy = (y1+y4)/2.0;
  // cout << cx << " " << cy << endl;
  cout << fixed << setprecision(15) << (double)cy/cx << endl;

  return 0;
}



Measured memory_bytes: 3300
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,s,n) for(int i = s; i < n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using Graph = vector<vector<int>>;
const int INF = 1000000007;
int main(){
  int n;
  cin >> n;
  vector<ll>v(n);
  rep(i,n)cin >> v[i];
  sort(all(v));
  ll ans = v[n - 1] - v[0];
  for(int i = 0,j = n - 2;i + 1 < j; ++i,--j)ans += v[j] - v[i];
  for(int i = 1,j = n - 1;i + 1 < j;++i,--j)ans += v[j] - v[i];
  if(n & 1)ans += max(v[n / 2 + 1] - v[n / 2],v[n / 2] - v[n / 2 - 1]);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4040
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
LL gi () {
    LL ret=0; char ch=getchar();
    while((ch<'0' || ch>'9') && ch!='-') ch=getchar();
    char c=ch=='-'?getchar():ch;
    while(c>='0' && c<='9') ret=ret*10+c-'0',c=getchar();
    return ch=='-'?-ret:ret;
}
const int N = 50000 + 10;
int n,b[N],mx[N];
struct line {
    int A,B,C,id; LD k;
} a[N];
bool cmp (const line &x, const line &y) {
    return x.k < y.k;
}
int lowbit (int x) { return (x&(-x)); }
void upd (int x) {
    for(int i=x;i<=n;i+=lowbit(i)) mx[i] += 1;
}
int query (int x) {
    int ret = 0;
    for(int i=x;i;i-=lowbit(i)) ret += mx[i];
    return ret;
}
int calc (LD x) {
    for(int i=1;i<=n;i+=1) a[i].k = (-a[i].A * x - a[i].C) / a[i].B;
    sort(a+1,a+n+1,cmp);
    memset(mx,0,sizeof(mx));
    int ret = 0;
    for(int i=n;i>=1;i-=1) {
        ret += query(a[i].id); upd(a[i].id);
    }
    return ret;
}
int calc2 (LD y) {
    for(int i=1;i<=n;i+=1) a[i].k = (-a[i].B * y - a[i].C) / a[i].A;
    sort(a+1,a+n+1,cmp);
    memset(mx,0,sizeof(mx));
    int ret = 0;
    for(int i=n;i>=1;i-=1) {
        ret += query(a[i].id); upd(a[i].id);
    }
    return ret;
}
int main () {
    n = gi(); int C = (n*(n-1)/2-1)/2+1;
    for(int i=1;i<=n;i+=1) a[i].A = gi(), a[i].B = gi(), a[i].C = -gi(), a[i].k = (LD)a[i].A/a[i].B;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i+=1) a[i].id = i;
    LD l = -1e10+0.00149, r = 1e10-0.00198, mid;
    while(r-l > 1e-10) {
        mid = (l+r) / 2;
        if(calc(mid) < C) l = mid;
        else r = mid;
    }
    printf("%.10LF ",mid);
    for(int i=1;i<=n;i+=1) a[i].k = (LD)a[i].B/a[i].A;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i+=1) a[i].id = i;
    l = -1e10+0.00149, r = 1e10-0.00198, mid;
    while(r-l > 1e-10) {
        mid = (l+r) / 2;
        if(calc2(mid) < C) l = mid;
        else r = mid;
    }
    printf("%.10LF",mid);
    return 0;
}

Measured memory_bytes: 1664