akhauriyash/Code-Regression huggingface dataset:
// in case of multiple test cases and N=1e5 don't intialize arrays as global except for graph vector-array
// always check whether or not you are doing mod of a negative number
// always use 1LL instead of 1
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace __gnu_pbds;
using namespace std;

#define double      	long double
#define int         	long long
#define pb          	push_back
#define pii         	pair<int,int>
#define vi          	vector<int>
#define vii         	vector<pii>
#define mi          	unordered_map<int,int>
#define mii         	map<pii,int>
#define all(a)      	(a).begin(),(a).end()
#define sz(x)       	(int)x.size()
// just comment the line below in case of interactive problems
#define endl        	"\n"
#define repp(i,a,b) 	for(int i=a;i<b;i++)
#define rep(i,a,b) 		for(int i=a;i<=b;i++)
#define brep(i,a,b)     for(int i=a;i>=b;i--)
#define deb1(x)      	cout << #x << "=" << x << endl
#define deb2(x, y)  	cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z)  	cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define trace(v) 		for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
#define tracearr(a,l,r) for(int iii=l;iii<=r;iii++)cout << a[iii] << " ";cout << endl;
#define PI          	3.1415926535897932384626
#define F 				first
#define S 				second
#define clr(x,y) 		memset(x, y, sizeof(x))
#define IOS         	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
// *s.find_by_order(1) - gives the 2nd samllest element in set
// s.order_of_key(x)   - gives the number of elements in the set which are strictly smaller than x


const int N=3e5 + 5;
const int MOD=1e9 + 7;

int n,m,k;
int row[N];
int col[N];

int32_t main()
{
	IOS;
	int T=1;
	//cin >> T;
	// int numOfSetBits = __builtin_popcountll(n);
	std::cout << std::fixed << std::setprecision(12);
	while(T--)
	{
		cin >> n >> m >> k;
		int maxr = 0;
		int maxc = 0;
		mii mp;
		rep(i,1,k)
		{
			int x,y;
			cin >> x >> y;
			row[x]++;
			col[y]++;
			maxr = max(maxr,row[x]);
			maxc = max(maxc,col[y]);
			mp[{x,y}]=1;
		}
		vi all_rows;
		vi all_cols;
		rep(i,1,n)
		{
			if(row[i]==maxr)
				all_rows.pb(i);
		}
		rep(i,1,m)
		{
			if(col[i]==maxc)
				all_cols.pb(i);
		}
		for(int x: all_rows)
		{
			for(int y: all_cols)
			{
				if(mp[{x,y}]==0)
				{
					cout << maxr + maxc;
					return 0;
				}
			}
		}
		cout << maxr + maxc - 1;
	}
}

Measured memory_bytes: 35052
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int,int> P;
int main(void){
  int n,i,a,ans=0;
  map<int,int> m;
  map<int,int>::iterator ite;
  cin >> n;
  for (i=0;i<n;i++){
    cin >> a;
    ite=m.find(a);
    if (ite==m.end()) m.insert(P(a,1));
    else ite->second++;
  }
  for (ite=m.begin();ite!=m.end();ite++){
    int f=ite->first,s=ite->second;
    if (s>=f) ans+=s-f;
    else ans+=s;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4736
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int di[][3] = {
	{0,1,2},{3,4,5},{6,7,8},
	{0,3,6},{1,4,7},{2,5,8},
	{0,4,8},{2,4,6}
};
int main(){
	string t;
	while(cin >> t , t != "0"){
		string ans = "NA";
		string s; s += t;
		rep(i,2)cin >> t , s+=t;
		rep(i,8){
			bool f = true;
			rep(j,3) f &= s[di[i][j]] == s[di[i][0]];
			if(f && s[di[i][0]] != '+'){
				ans = s[di[i][0]];
			}
		}
		cout << ans << endl;
	}
}

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

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

int main()
{
    bool BINGO = false;
    vector<vector<int>> bingo(3, vector<int>(3));
    rep(i, 3)
    {
        for (int j = 0; j < 3; j++)
            cin >> bingo.at(i).at(j);
    }
    int N;
    cin >> N;
    vector<int> b(N);
    rep(i, N) cin >> b.at(i);
    rep(i, N)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
            {
                if (b.at(i) == bingo.at(j).at(k))
                    bingo.at(j).at(k) = 0;
            }
        }
    }
    rep(i, 3)
    {
        if (bingo.at(0).at(i) == 0 && bingo.at(1).at(i) == 0 && bingo.at(2).at(i) == 0)
            BINGO = true;
        if (bingo.at(i).at(0) == 0 && bingo.at(i).at(1) == 0 && bingo.at(i).at(2) == 0)
            BINGO = true;
    }
    if (bingo.at(1).at(1) == 0)
    {
        if (bingo.at(0).at(0) == 0 && bingo.at(2).at(2) == 0)
            BINGO = true;
        if (bingo.at(0).at(2) == 0 && bingo.at(0).at(2) == 0)
            BINGO = true;
    }
    if (BINGO)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using vpii = vector<pii>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define rep2(i, s, n) for(int i=(s);i<(int)n;i++)
int INF=1e9+7;

int main() {
  int N;
  ll K;
  cin >> N >> K;
  vi A(N);
  rep(i,N) cin >> A[i];
  
  vl count(N),count2(N);
  rep(i,N) {
    rep(j,N) {
      if(A[i]>A[j]) {
        if(i<j) count[i]++;
        else count2[i]++;
      }
    }
  }
  ll ans=0;
  ll x=K*(K+1)/2%INF,y=K*(K-1)/2%INF;
  rep(i,N) {
    ans=(ans+count[i]*x%INF)%INF;
    ans=(ans+count2[i]*y%INF)%INF;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;

public class Hello{
    public static void Main(){

        int[] x = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int H = x[0];
        int W = x[1];
        
        for(int i = 0; i < H; i++){
            string str = Console.ReadLine();
            Console.WriteLine(str);
            Console.WriteLine(str);
        }
    }
}


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

using namespace std;

int main() {
  string s, t;
  cin >> s >> t;
  int ans = 1001;
  
  for(int i = 0; i < s.length() - t.length() + 1; i++) {
    int op = 0;
    for(int j = 0; j < t.length(); j++) {
      if(s[i + j] != t[j])
        op++;
    }
    if(ans > op)
      ans = op;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 3604
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

int main() {
	int i, j, k;
	int num;

	cin >> num;

	if (num < 3) {
		cout << "0" << endl;
		return 0;
	}
	else {
		cout << num / 3 << endl;
	}













	getchar();
	getchar();
	return 0;
}


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

using namespace std;

struct Point { double x, y; };

int main() {
    Point p[4];
    while (scanf("%lf %lf", &p[0].x, &p[0].y) != EOF) {
        for (int i = 1; i < 4; i++)
            scanf("%lf %lf", &p[i].x, &p[i].y);
        
        if (!((p[1].x < p[2].x) || (p[3].x < p[0].x)) && !((p[1].y < p[2].y) || (p[3].y < p[0].x)))
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}


Measured memory_bytes: 3148
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n = I()
num = LI()
ans = 0
ret = 0
for i in range(n-1):
    if num[i+1] <= num[i]:
        ret += 1
        ans = max(ret, ans)
    else:
        ret = 0


print(ans)



Measured memory_bytes: 60144
n = int(input())
ans=0
mp=[[0]*10 for _ in range(10)]
for i in range(1,n+1):
    a=int(str(i)[0])
    b=int(str(i)[-1])
    mp[a][b]+=1

for i in range(10):
    for j in range(10):
        ans+=mp[i][j]*mp[j][i]
    


print(ans)





Measured memory_bytes: 40684
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>

const long INF = (1l << 30);
const long LINF = (1l << 60);

typedef std::complex<double> Com;

//geometric library
//#include <complex>
//typedef complex<double> Com;
//c++ -std=c++14

//内積
double dot_product(const Com a, const Com b){
	return (conj(a)*b).real();
}
//外積
double cross_product(const Com a, const Com b){
	return (conj(a)*b).imag();
}
//点と直線の距離
double dist_dot_line(const Com st, const Com en, const Com dt){
    return std::abs(cross_product(dt-st, en-st) / std::abs(en-st));
}
//点と線分の距離
double dist_dot_seg(const Com st, const Com en, const Com dt){
	if(dot_product(en-st, dt-st) <= 0){
		return std::abs(dt-st);
	}else if(dot_product(st-en, dt-en) <= 0){
		return std::abs(dt-en);
	}else{
		return dist_dot_line(st, en, dt);
	}
}
//線分の交差判定
bool seg_crossing(const Com st1, const Com en1, const Com st2, const Com en2){
	double cross1 = cross_product(en1-st1, st2-st1) * cross_product(en1-st1, en2-st1);
	double cross2 = cross_product(en2-st2, st1-st2) * cross_product(en2-st2, en1-st2);
	return (cross1 <= 0) && (cross2 <= 0);
}
//線分と線分の距離
double dist_seg(const Com st1, const Com en1, const Com st2, const Com en2){
	if(seg_crossing(st1, en1, st2, en2)){
		return 0;
	}
	return std::min(std::min(dist_dot_seg(st1, en1, st2), dist_dot_seg(st1, en1, en2)), std::min(dist_dot_seg(st2, en2, st1), dist_dot_seg(st2, en2, en1)));
}

Com p1, p2;
long q;
Com p;

int main(){
    double xp1, yp1, xp2, yp2;
    scanf("%lf%lf%lf%lf", &xp1, &yp1, &xp2, &yp2);
    p1 = Com(xp1, yp1);
    p2 = Com(xp2, yp2);
    scanf("%ld", &q);
    for(int i = 0; i < q; i++){
        double x, y;
        scanf("%lf%lf", &x, &y);
        p = Com(x, y);
        Com a = p - p1;
        Com b = p2 - p1;
        Com proj = dot_product(a, b) / (std::abs(b) * std::abs(b)) * b;
        Com ans = proj*2.0 - a + p1;
        printf("%.10lf %.10lf\n", real(ans), imag(ans));
    }
}



Measured memory_bytes: 3284
N = int(input())
E = [[] for _ in range(N)]

for _ in range(N-1):
	u,v,w = map(int,input().split())
	u -= 1
	v -= 1
	E[u].append((v,w))
	E[v].append((u,w))

color = [-1 for _ in range(N)]
stack = [u]
color[u] = 0
while stack:
	u = stack.pop()
	for v,w in E[u]:
		if color[v] == -1:
			stack.append(v)
		if w % 2 == 0:
			color[v] = color[u]
		else:
			color[v] = (color[u] + 1) % 2

for i in range(N):
	print(color[i])



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

int main(){
	bool prime[10001];
	for(int i=2; i<=10000; ++i) prime[i]=true;
	prime[1]=false;
	for(int i=2; i<=10000; ++i)
		if(prime[i]) for(int j=2; i*j<=10000; ++j) prime[i*j]=false;
	
	int n;
	while(scanf(" %d", &n) != EOF){
		int ans=0;
		for(int i=1; i<=n; ++i)
			if(prime[i] && prime[n-i+1]) ++ans;
		
		printf("%d\n", ans);		
	}
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define each(i, mp) for (auto &i : mp)
#define sz(x) int(x.size())

const double PI = acos(-1);

int main()
{
  int a, b, h, m;
  cin >> a >> b >> h >> m;
  double th = double(h * 60 + m) / 720 * 2 * PI;
  double tm = double(m) / 60 * 2 * PI;
  double xh = a * cos(th), yh = a * sin(th);
  double xm = b * cos(tm), ym = b * sin(tm);
  double dx = xh - xm, dy = yh - ym;
  double ans = sqrt(dx * dx + dy * dy);
  printf("%.10f\n", ans);
  return 0;
}


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

using ll = long long;
using p = pair<ll, ll>;
constexpr ll INF = 1LL << 62;

int main(void) {
  ll N;

  cin >> N;

  ll ans = (1000 - N % 1000) % 1000;
  cout << ans << endl;
  return 0;
}


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

int main(){
        int n,k,minimum;cin>>n>>k;
        ll a[n],dp[n];memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)cin>>a[i];

        for(int i=1;i<n;i++)
        {
            minimum=INT_MAX;
            for(int j=i-1;j>=0&&j>=i-k;j--)
            {
                minimum=min(ll(minimum),dp[j]+abs(a[j]-a[i]));
            }
            dp[i]=minimum;
        }
        cout<<dp[n-1];
	return 0;
}




Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (a == b) {
            System.out.println("Draw");
        } else if ((a > b && b != 1) || a == 1) {
            System.out.println("Alice");
        } else {
            System.out.println("Bob");
        }
    }

}

Measured memory_bytes: 9812
##### 解けた #####

g1=[1,3,5,7,8,10,12]
g2=[4,6,9,11]
g3=[2]

x,y=list(map(int,input().split(" ")))

if ((x in g1) and (y in g1)) or ((x in g2) and (y in g2)) or ((x in g3) and (y in g3)):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
import java.util.*;

class Main {
  public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  Integer array[] = new Integer[n] ;
  for(int i=0; i<n; i++){
    array[i] = sc.nextInt();
  }
  int count =0;
  int max = array[0];
  for(Integer elem:array){
    if (elem >= max){
      count += 1;
      max = elem;
    }
  }
  System.out.println(count);
  }
}

Measured memory_bytes: 21844
#include<stdio.h> 

#define MAXLEN 10000    
     
int main( void ) 
{
	int n,q;
	int S[ MAXLEN+1 ],T[ MAXLEN+1 ];
	int i,j;
	int cnt;    
	
	scanf( "%d", &n ); 
	for( i=0; i<n; i++ ) {
		scanf( "%d", &S[i] ); 
	}
	
	cnt=0;
	scanf( "%d", &q ); 
	for( i=0; i<q; i++ ) {
		scanf( "%d", &T[i] );
		for( j=0; j<n; j++ ) {
			if( T[i] == S[j] ) {
				cnt++;
				break;
			}
		}
	}
	
	if( cnt ) {
		printf( "%d\n", cnt );
	} else {
		printf( "0\n" );
	}
	
	return 0;
}

Measured memory_bytes: 644
n, k = [int(x) for x in input().split()]

array = []

for i in range(n):
  a_b = [int(x) for x in input().split()]
  array.append(a_b)

array.sort()
index = 0
for a_b in array:
  index += a_b[1]
  if index >= k:
    print(a_b[0])
    break

Measured memory_bytes: 21652
#include <algorithm>
#include <chrono>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>

using namespace std;

int MOD;

inline void ModMul(int& x, int y)
{
    x = (1LL * x * y) % MOD;
}

inline int GetModMul(int x, int y)
{
    ModMul(x, y);
    return x;
}

inline void ModSum(int& x, int y)
{
    x += y;
    if (x < 0) {
        x += MOD;
    }
    if (x >= MOD) {
        x -= MOD;
    }
}

inline int GetModSum(int x, int y)
{
    ModSum(x, y);
    return x;
}

const int MAX_N = 2e3;

int n;

void Solve()
{
    vector<int> a[4];
    for (int i = 0; i < 4; ++i) {
        a[i].assign(6 * n + 1, 0);
    }
    int curPtr = 0;
    a[curPtr][3 * n] = 1;
    for (int i = 1; i <= 3 * n; ++i) {
        int nxtPtr = curPtr + 1;
        if (nxtPtr >= 4) {
            nxtPtr = 0;
        }
        a[nxtPtr].assign(6 * n + 1, 0);
        int prevPtr = curPtr - 1;
        if (prevPtr < 0) {
            prevPtr += 4;
        }
        int prevPrevPtr = prevPtr - 1;
        if (prevPrevPtr < 0) {
            prevPrevPtr += 4;
        }
        for (int j = 0; j <= 6 * n; ++j) {
            if (j > 0) {
                ModSum(a[nxtPtr][j - 1], a[curPtr][j]);
            }
            if (j + 1 <= 6 * n) {
                ModSum(a[nxtPtr][j + 1], GetModMul(i - 1, a[prevPtr][j]));
            }
            ModSum(a[nxtPtr][j], GetModMul((1LL * (i - 1) * (i - 2)) % MOD, a[prevPrevPtr][j]));
        }
        curPtr = nxtPtr;
    }
    int result = 0;
    for (int i = 0; i <= 6 * n; ++i) {
        int sum = i - 3 * n;
        if (sum <= 0 && abs(sum) % 3 == 0) {
            ModSum(result, a[curPtr][i]);
        }
    }
    cout << result << endl;
}

bool Read()
{
    if (!(cin >> n >> MOD)) {
        return false;
    }
    return true;
}

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

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    while (Read()) {
        Solve();
    }

    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,k,sum=0;
    vector<int> a;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int b;
        cin>>b;
        a.push_back(b);
    }
    for(int i=0;i<k;i++){
        int min=1000000,y;
        for(int j=0;j<a.size();j++){
            if(min>a[j]){
                min=a[j];
                y=j;
            }
        }
        sum+=min;
        a.erase(a.begin()+y);
    }
    cout<<sum;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,P;cin>>N;
  set<int> a;
  for(int i=0;i<N;i++){
    cin>>P;
    if(a.count(P))a.erase(P);
    else a.insert(P);
  }
  cout<<a.size()<<endl;
}

Measured memory_bytes: 4864
import java.util.Scanner;
import java.util.Vector;

class Main {
    public static void main(String[] args) {
        Scanner ler = new Scanner(System.in);
        long a = ler.nextLong(), b = ler.nextLong(), c = ler.nextLong(), d = ler.nextLong();
        Vector<Long> v = new Vector<>();

        v.add(a*c);
        v.add(a*d);
        v.add(b*c);
        v.add(b*d);
        v.sort(null);

        System.out.println(v.lastElement());
    }   
}


Measured memory_bytes: 35680
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define INIT(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define INIT2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}


int main(){
  ll N; cin>>N;
  ll a[N]; CINA(a,N);
  ll d[N+1];
  for(int i=0;i<N+1;i++){
    if(i==0){d[0] = abs(a[0]);continue;}
    if(i==N){d[N] = abs(a[N-1]);continue;}
    d[i] = abs(a[i]-a[i-1]);
  }
  
  ll s = sum(d,N+1);
  REP(i,N){
    ll r;
    if(i==0){ r = s - (d[0]+d[1]) + abs(a[1]);}
    else if(i==N-1){ r = s - (d[N-1]+d[N]) + abs(a[N-2]);}
    else{r = s - (d[i]+d[i+1]) + abs(a[i+1]-a[i-1]);}
    cout << r <<"\n";
  }
}

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

using namespace std;

int main(){
	string s; cin >> s;
	vector<bool> seq;
	vector<int> R;
	vector<int> L;
	for(int i = 0; i < s.length(); i++){
		seq.push_back(s[i] == 'R');
		if(s[i] == 'R')
			R.push_back(i);
		else
			L.push_back(i);
	}
	
	int nextDiff = s.length() - 1;
	vector<int> result(s.length(), 0);

	for(int i = R.size() - 1; i >= 0; i--){
		if(seq[R[i]+1]){ // the right is R
			int d = nextDiff - R[i];
			if(d & 1){
				result[nextDiff-1]++;
			} else {
				result[nextDiff]++;
			}
		}
		else{ //the right is L
			nextDiff = R[i] + 1;
			result[nextDiff-1]++;
		}
	}

	for(int i = 0; i < L.size(); i++){
		if(seq[L[i]-1]){ // the left is R
			nextDiff = L[i] - 1;
			result[nextDiff+1]++;
		} else { //the left is L
			int d = L[i] - nextDiff;
			if(d & 1){
				result[nextDiff+1]++;
			} else {
				result[nextDiff]++;
			}
		}
	}

	for(auto x : result){
		printf("%d ", x);
	}
	printf("\n");

	return 0;
}



Measured memory_bytes: 4408
n=int(input())
a=[0]*n
b=[0]*n
c=[0]*n
for i in range(n):
    a[i],b[i],c[i]=list(map(int,input().split()))
dpa=[100000000]*n
dpb=[100000000]*n
dpc=[100000000]*n
dpa[0]=a[0]
dpb[0]=b[0]
dpc[0]=c[0]
for i in range(n-1):
    dpa[i+1]=max(dpb[i]+a[i+1],dpc[i]+a[i+1])
    dpb[i+1]=max(dpa[i]+b[i+1],dpc[i]+b[i+1])
    dpc[i+1]=max(dpa[i]+c[i+1],dpb[i]+c[i+1])


print(max(dpa[n-1],dpb[n-1],dpc[n-1]))



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

class Program
{
    static void Main(string[] args)
    {
        var s = Console.ReadLine();

        var output = 0;
        for (int i = 0; i < s.Length / 2.0; i++)
        {
            if (s[i] != s[s.Length - 1 - i])
                output++;
        }

        Console.WriteLine(output);
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (const string& e_) { return "\"" + e_ + "\""; }
string to_string (char e_) { return "\'" + string(1, e_) + "\'"; }
string to_string (bool e_) { return e_ ? "true" : "false"; }
template <typename T> string to_string (T e_) {
	string s_ = "[ ";
	for (const auto& x_ : e_) s_ += to_string(x_) + " ";
	return s_ + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e_) {
	return "(" + to_string(e_.first) + ", " + to_string(e_.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
const int N = 100010;
int a[N];

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	int n, ans = 0;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a+n);
	
	if(n&1) ans = 0;
	else ans = a[n/2] - a[n/2 - 1];

	cout << ans;
}	

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;
typedef long long ll;
ll a[100];

int main()
{
    int n,i;

    a[0] = 2,a[1] = 1;
    for(i = 2;i <= 86;i++)
    {
        a[i] = a[i-1]+a[i-2];
    }

    while(scanf("%d",&n) != EOF)
    {
        printf("%lld\n",a[n]);
    }

    return 0;
}




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

using namespace std;
int main()
{
    int n;cin>>n;
    string s;cin>>s;
    
    int ans=0;
    for(int i=0;i<1000;++i){
        char a = (char)('0'+i/100);
        char b = (char)('0'+i%100/10);
        char c = (char)('0'+i%10);
        
        int aj=-1;int bj=-1;int cj=-1;
        for(int j=0;j<s.size();++j){
            if(aj==-1&&s[j]==a)aj=j;
            if(aj!=-1&&bj==-1&&aj<j&&s[j]==b)bj=j;
            if(bj!=-1&&cj==-1&&bj<j&&s[j]==c){++ans;break;}
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, N) for(ll i=0; i<N; ++i)

ll max(ll a, ll b) {return a < b ? b : a; }

int main() {
  string S, T;
  int A , B;
  string U;
  cin >> S >> T;
  cin >> A >> B;
  cin >> U;
  if(S == U) {
    cout << (A - 1) << " " << B << endl;
  } else {
    cout << A << " " << (B - 1) << endl;
  }
  
  return 0;
}

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

using namespace std;

char moji(char t,int cnt){
  if(t=='1'){
    cnt%=5;
    if(cnt==1) return '.';
    if(cnt==2) return ',';
    if(cnt==3) return '!';
    if(cnt==4) return '?';
    return ' ';
  }
  if(t=='2'){
    cnt%=3;
    if(cnt==1) return 'a';
    if(cnt==2) return 'b';
    return 'c';
  }
  if(t=='3'){
    cnt%=3;
    if(cnt==1) return 'd';
    if(cnt==2) return 'e';
    return 'f';
  }
  if(t=='4'){
    cnt%=3;
    if(cnt==1) return 'g';
    if(cnt==2) return 'h';
    return 'i';
  }
  if(t=='5'){
    cnt%=3;
    if(cnt==1) return 'j';
    if(cnt==2) return 'k';
    return 'l';
  }
  if(t=='6'){
    cnt%=3;
    if(cnt==1) return 'm';
    if(cnt==2) return 'n';
    return 'o';
  }
  if(t=='7'){
    cnt%=4;
    if(cnt==1) return 'p';
    if(cnt==2) return 'q';
    if(cnt==3) return 'r';
    return 's';
  }
  if(t=='8'){
    cnt%=3;
    if(cnt==1) return 't';
    if(cnt==2) return 'u';
    return 'v';
  }
  if(t=='9'){
    cnt%=4;
    if(cnt==1) return 'w';
    if(cnt==2) return 'x';
    if(cnt==3) return 'y';
    return 'z';
  }
}

int main() {
  int n; cin >> n;
  string s;
  for(int i=0;i<n;++i) {
    cin >> s;
    int cnt=0;
    char t;
    for(int j=0;j<s.size();++j){
      if(s[j]=='0' && cnt) {
	cout << moji(t,cnt);
	cnt=0;
      } else if(s[j]!='0') t=s[j],cnt++;
    }
    cout << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3052
#include <bits/stdc++.h> 
using namespace std;
int main(){
  int i,n,l[102],m,s=0;
  cin>>n>>m;
  for(i=0;i<n;i++)
    cin>>l[i];
  for(i=0;i<n;i++){
    s+=l[i];
    if(s>m) break;
  }
  cout<<i+1;
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

N,M = list(map(int, input().rstrip().split()))
#-----
ans = []
delta = 0
visited = set()


for i in range(M):
    L = 1+i
    R = N-i
    diff = (R - delta) - L
    
    if (2*diff == N) or \
       (diff in visited) or ((N - diff) in visited):
       
        delta = 1
    
    ans.append( [L, R - delta] )
    visited |= {diff , (N - diff)}


for nums in ans:
    print(*nums)


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


#define FOR(i,a,b) for(ll i = a ; i < b ; i++) // for i in range(a,b)
#define REP(i,n) for(ll i = 0 ; i < n ; i++) // for i in range(b)
#define FORD(i,a,b) for(ll i = a ; i > b ; i--) // for i in range(a,b,-1)
#define ALL(x) x.begin(),x.end()
#define debug(x) cerr << #x << ": " << x << '\n'

const int IINF = 1'001'001'001;
const ll INF = 1'001'001'001'001'001'001ll;
const int MOD = 1'000'000'007;


void solve(){
    string s; cin >> s;
    int ans = 0;
    int cnt = 0;
    REP(i,s.size()){
        debug(i);
        if(i%2==0 && s[i]=='0') cnt+=1;
        else if(i%2==1 && s[i]=='1') cnt+=1;
    }
    ans = cnt;
    cnt = 0;
    REP(i,s.size()){
        if(i%2==0 && s[i]=='1') cnt+=1;
        else if(i%2==1 && s[i]=='0') cnt+=1;
    }
    ans = min(ans,cnt);
    cout << ans << endl;
}

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

Measured memory_bytes: 3728
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// DONT USE MEMSET, USE VECTORS

vector<ll> a;
int n; ll x;

ll check(){
	ll cnt = 0;
	ll red = 0;
	for(int i=0; i<n-1;i++){
		ll p = a[i] + a[i+1] - red;
		if(p <= x) {
			red = 0;
			continue;
		}
		cnt += p-x;
		// cout<<i<<" "<<p-x<<endl;
		red = min(p-x, a[i+1]);
	}
	return cnt;
}

void solve(){
	cin>>n>>x;
	a.resize(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}

	cout<<check()<<endl;
	// ll l = 0;
	// ll h = 1e15;
	// ll ans = -1;
	// while(l<=h){
	// 	ll m = l + (h-l)/2;
	// 	if(check(m)){
	// 		ans = m;
	// 		h = m-1;
	// 	}
	// 	else{
	// 		l = m+1;
	// 	}
	// }

}

int main(){
	fastread;
	int t = 1;
	// cin>>t;
	for(int i=1;i<=t;i++){
		// cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <istream>
#include <ostream>

#include <cstdlib>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i,n) for(ll i=0; i < (n); ++i)
#define rrep(i,n) for(ll i=((n)-1); i >= 0; --i)

#define OPLT(T) bool operator<(const T & lop_, const T & rop_)
#define OPEQ(T) bool operator==(const T & lop_, const T & rop_)

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

istream& operator>>(istream& istr, __float128& obj) { double d; istr >> d; obj = d; return istr; };
ostream& operator<<(ostream& ostr, __float128& obj) { ostr << static_cast<double>(obj); return ostr; };

ll res[510][510];

const ll absmx = 1e9;

int main() {
	ll H, W, h, w;
	cin >> H >> W >> h >> w;
	bool flg = false;
	for(int k = 0; k < 2; k++) {
		if(h*w == 1) break;
		ll d;
		if(k == 0) {
			d = (absmx-1) / (h*w-1);
		}
		else {
			d = (absmx+1) / (h*w-1);
		}

		rep(i,510) {
			rep(j,510) {
				if(k == 0)
					res[i][j] = 1*d;
				else
					res[i][j] = -1*d;
			}
		}

		if(k == 0) {
			for(int i = h-1; i < H; i += h) {
				for(int j = w-1; j < W; j += w) {
					res[i][j] = - ((h*w-1)*d +1);
				}
			}
		}
		else {
			for(int i = 0; i < H; i += h) {
				for(int j = 0; j < W; j += w) {
					res[i][j] = (h*w-1)*d-1;
				}
			}
		}

		ll sum = 0;
		rep(i,H) {
			rep(j,W) {
				sum += res[i][j];
			}
		}
		if(sum > 0) {
			flg = true;
			break;
		}
	}

	if(flg) {
		cout << "Yes" << endl;
		rep(i,H) {
			rep(j,W) {
				if(j) cout << " ";
				cout << res[i][j];
			}
			cout << endl;
		}
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 4992
def main():
    n, q = map(int, input().split())
    S = input()

    N = [0] * (n + 1)
    for i in range(n):
        N[i + 1] = N[i] + (1 if S[i:i + 2] == 'AC' else 0)

    print()
    
    for j in range(q):
        l, r = map(int, input().split())
        
        print(N[r-1] - N[l-1])
    
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 7748
import java.util.Scanner;

public class Main {

	static Scanner scanner;
	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int n=gi();
	    int[] a= new int[n-1];
	    
	    for (int i=0; i<n-1; i++) {
	    	a[i]=gi();
	    }
	    
	    int[] b=new int[n];
	    for (int i=0; i<n-1; i++) {
	    	b[a[i] - 1]++;
	    }

	    for (int i=0; i<n; i++) {
	    	System.out.println(b[i]);
	    }
        //System.out.println(Math.pow(l/3, 3));
//        if (a<b) {
//        	System.out.print(Math.max(b-a-w, 0));
//        }else {
//        	System.out.print(Math.max(a-b-w, 0));
//        }


	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

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

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

Measured memory_bytes: 3632
# Vicfred
# https://atcoder.jp/contests/abc154/tasks/abc154_a
# simulation
s, t = input().split()
a, b = list(map(int, input().split()))
u = input()

balls = {}
balls[s] = a
balls[t] = b
balls[u] = balls[u] - 1

print(balls[s], balls[t])



Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

const int N = 1e5 + 8;
const int INF = 1e17 + 239;

int used[N];
int val[N];
int h[N];
vector<pair<int, int>> g[N];

int fl = 0;
set<int> ss;

void dfs(int cur, int cs, int ch) {
	val[cur] = cs;
	h[cur] = ch;
	used[cur] = 1;
	for (auto t : g[cur]) {
		if (!used[t.first]) {
			dfs(t.first, t.second - val[cur], ch + 1);
		} else {
			if ((h[cur]) % 2 == h[t.first] % 2) {
				int rv = t.second - (val[cur] + val[t.first]);
				if (h[cur] % 2) rv *= -1;
				if (rv % 2 != 0) {
					cout << 0 << endl;
					exit(0);
				}
				ss.insert(rv);
			} else {
				fl |= (val[cur] + val[t.first] != t.second);
			}
		}
	}
}

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

	int n, m;
	cin >> n >> m;
	while (m--) {
		int u, v, s;
		cin >> u >> v >> s;
		u--;
		v--;
		s -= 2;
		g[u].push_back({v, s});
		g[v].push_back({u, s});
	}
	dfs(0, 0, 0);
	for (int i = 0; i < n; i++) assert(used[i]);
	if (fl) {
		cout << 0 << endl;
		exit(0);
	}
	if (!ss.empty()) {
		if ((int)ss.size() == 1) {
			for (int i = 0; i < n; i++) {
				if (h[i] % 2 == 0) val[i] += *ss.begin() / 2;
				else val[i] -= *ss.begin() / 2;
			}
			int ok = 1;
			for (int i = 0; i < n; i++) {
				for (auto j : g[i]) {
					ok &= (val[i] + val[j.first] == j.second);
				}
			}
			for (int i = 0; i < n; i++) {
				ok &= (val[i] >= 0);
			}
			cout << ok << endl;
		} else {
			cout << 0 << endl;
		}
		return 0;
	} 
	//-mn0 
	//mn1
	int mn0 = INF;
	int mn1 = INF;
	for (int i = 0; i < n; i++) {
		if (h[i] % 2 == 0) mn0 = min(mn0, val[i]);
		else mn1 = min(mn1, val[i]);
	}
	mn0 *= -1;
	// cerr << mn0 << ' ' << mn1 << endl;
	if (mn0 <= mn1) {
		cout << mn1 - mn0 + 1 << endl;
	} else {
		cout << 0 << endl;
	}
}


Measured memory_bytes: 18048
n,a,b=gets.chomp.split.map(&:to_i)
l=a+b
c_1,c_2=[0,0]
s=gets.chomp.to_s
(0..n-1).each do |i|
  case s[i]
  when "a"
    if c_1 < l
      puts "Yes"
      c_1 += 1
    else
      puts "No"
    end
  when "b"
    if (c_1<l)&&(c_2<b)
      puts "Yes"
      c_1 += 1
      c_2 += 1
    else
      puts "No"
    end
  when "c"
    puts "No"
  end
end


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

using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugst(x) auto xt = copy(x);cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl

constexpr lli MOD = (lli)1e9 + 7;
constexpr lli LIMIT = 1000000000000000000 * 5;

int main() {
	int N;
	cin >> N;
	set<string> se;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		se.insert(s);
	}
	cout << se.size() << endl;
	return 0;
}



Measured memory_bytes: 19256
def elip():
    return map(int,input().split())
N = int(input())
D = list(elip())
Semi = 0
i = 0
D.sort()
while i != N//2:
    Semi = D[i]
    i += 1
if len([el for el in D if el > Semi]) != N//2:
    print(0)
else:
    print(min([el for el in D if el > Semi])-Semi)

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

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

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

int h, w, a, b;
int f[200000];

int add(int a, int b){
	return (a + b) % mod;
}
int mul(int a, int b){
	return ll(a) * b % mod;
}
int pow(int a, int k){
	int b = 1;
	while(k > 0){
		if(k & 1){
			b = mul(b, a);
		}
		a = mul(a, a);
		k >>= 1;
	}
	return b;
}
int inv(int a){
	return pow(a, mod - 2);
}

void clcf(){
	f[0] = 1;
	for(int i = 1; i < 200000; ++i){
		f[i] = mul(f[i - 1], i);
	}
}

int cmb(int a, int b){
	return mul(f[a], inv(mul(f[b], f[a - b])));
}
int pth(int a, int b){
	return cmb(a + b, a);
}

int main(){
	cin >> h >> w >> a >> b;
	
	clcf();

	int ans = 0;
	rep(i, h - a){
		int p = pth(b - 1, i);
		int q = pth(w - b - 1, h - i - 1);
		ans = add(mul(p, q), ans);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

    int k;
    string s;
    cin >> k >> s;
    int n = s.length();
    if(n <= k){
        cout << s << endl;
        return 0;
    }
    string ans = s.substr(0, k);
    for(int i = 0; i < 3; ++i){
        ans += '.';
    }
    cout << ans << endl;
}

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

using namespace std;

#define maxn 2000005
#define ll long long int
#define db(x) cout<<#x<<" -> "<<x<<endl
#define db2(x,y) cout<<#x<<" -> "<<x<<" , "<<#y<<" -> "<<y<<endl
#define db3(x,y,z) cout<<#x<<" -> "<<x<<" , "<<#y<<" -> "<<y<<" , "<<#z<<" -> "<<z<<endl
#define prt(x) for(auto it = x.begin(); it!=x.end(); it++){cout<<*it<<" " ;}cout<<endl

namespace NumberTheory{
    const ll mod = (ll)1e9+7;
    ll fact[maxn+5];
    ll inverseFact[maxn+5];
    vector< int > Prime;
    bool vis[maxn+5];
    void seive(){
        for(int i=2; i*i<=maxn; i++){
            if(vis[i]==0){
                for(int j=(2*i); j<=maxn; j+=i){
                    vis[j] = true;
                }
            }
        }
        Prime.push_back(2);
        for(int i=3; i<=maxn; i+=2){
            if(vis[i]==0){
                Prime.push_back(i);
            }
        }
    }

    ll bigmod(ll a, ll n){
        if( n==0 ) { return 1LL; }
        if( n%2==0 ){
            ll ret = bigmod(a,n/2);
            return ( (ret%mod) * (ret%mod) ) % mod;
        }
        else { return ( ( a % mod ) * ( bigmod(a,n-1) % mod ) ) % mod ; }
    }

    ll modInverse(ll a){
        return bigmod(a,mod-2)%mod;
    }

    ll nCr(int n, int r){
        ll ans = (1LL*(fact[n] * inverseFact[r])%mod * inverseFact[n-r]) % mod ;
        return (ans%mod);
    }

    void PreProcess(){
        fact[0] = 1LL;
        for(int i=1; i<=maxn; i++){ fact[i] = (  1LL * fact[i-1] *  i )  % mod ; }
        inverseFact[maxn] = modInverse(fact[maxn]) ;
        for(int x=maxn-1 ; x>=0 ; x--) inverseFact[x] = ( 1LL * inverseFact[x+1] * (x+1) ) % mod ;
    }

    vector< pair< int , int >  > f(int x){
        vector< pair< int , int > > temp;
        for(int i=0; Prime[i]*Prime[i]<=x; i++){
            if(x%Prime[i]==0){
                int cnt = 0;
                while(x%Prime[i]==0){
                    cnt++;
                    x/=Prime[i];
                }
                temp.push_back( make_pair(Prime[i],cnt) );
            }
        }
        if(x>1){
            temp.push_back(make_pair(x,1));
        }
        return temp;
    }
}

int main(){
    ios_base::sync_with_stdio(false) ;
    cin.tie(0);
//    freopen("input.txt","r",stdin);
    using namespace NumberTheory ;
    int n, m , k;
    cin>>n>>m>>k;
    ll ans = 0LL ;
    PreProcess() ;
    for(int i=1; i<=(n-1); i++){
        ans+=( ( (1LL * i * (n-i) ) % mod ) * ( ( m % mod * m % mod ) ) % mod ) % mod  ;
        ans%=mod ;
    }
    for(int i=1; i<=(m-1); i++){
        ans+=( ( (1LL * i * (m-i) ) % mod ) * ( ( n % mod * n % mod ) ) % mod ) % mod ;
        ans%=mod ;
    }
    ans%= mod ;
    ll ret = nCr((1LL * n * m)-2 , k-2);
    ans = ( ans % mod  * ( ret % mod ) ) % mod ;
    cout<<ans<<endl;
    return 0 ;
}


Measured memory_bytes: 31488
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int n,k,q;
vector<ll> v;

ll solve(ll x){

  vector<ll> t;
  for(int i=0;i<v.size();i++){
    if(v[i]>=x){
      vector<ll> w;
      for(;i<v.size()&&v[i]>=x;i++){
        w.push_back(v[i]);
      }
      if(w.size()>=k){
        sort(w.begin(),w.end());
        for(int j=0;j+k-1<w.size();j++){
          t.push_back(w[j]);
        }
      }
    }
  }

  if(t.size()<q) return -1;
  else{
    sort(t.begin(),t.end());
    return t[q-1];
  }
}

int main(){
  cin>>n>>k>>q;
  for(int i=0;i<n;i++){
    ll a;
    cin>>a;
    v.push_back(a);
  }

  ll ans=1e9;
  for(int i=0;i<n;i++){
    ll z=solve(v[i]);
    if(z==-1) continue;
    ans=min(ans,z-v[i]);
  }

  cout<<ans<<endl;


  return 0;
}


Measured memory_bytes: 256
import collections
dump = input()
inp = list(map(int,input().split()))
A = collections.Counter(inp)
t_A = [el[0] for el in A.items() if el[1] > 1]
t_A.extend([el[0] for el in A.items() if el[1] > 3])
t_A = sorted(t_A)
if len(t_A) >= 2:
  print(t_A[-2]*t_A[-1])
else:
  print(0)

Measured memory_bytes: 18600
#include<iostream>
#include<cmath>
#include<complex>
#include<numeric>
using namespace std;
int gcd(int u, int v) {
	int r;
	while (0 != v) {
		r = u % v; u = v; v = r; /* swap */
	}
	return u;
}

int main()
{
	int N, X, x[100010],ans;
	cin >> N >> X;
	for (int i = 0; i < N; i++) {
		cin >> x[i];
	}
	ans = abs(x[0] - X);
	for (int i = 0; i < N - 1; i++) {
		ans = gcd(ans,abs(x[i+1]-x[i]));
	}
	cout << ans << endl;

	system("pause");
    return 0;
}



Measured memory_bytes: 888
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		String S = sc.next();
		String now = S.substring(0, 1);
		int ans = 1;
		for(int i = 1; i < N; i++) {
			if(!now.equals(S.substring(i, i + 1))) {
				ans++;
			}
			now = S.substring(i, i + 1);
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 34272
/// In The Name Of God
 
#include <bits/stdc++.h>
 
#define f first
#define s second
 
#define pb push_back
#define pp pop_back
#define mp make_pair
 
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
 
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
 
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
#define nl '\n'
#define ioi exit(0);
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
 
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
 
using namespace std;
 
int h, w, n;
char s[N], t[N];
 
 
int f(int x, int y) {
	return min(min(y, h - y), min(x, w - x));
}
 
pair <int, int> nxt(char c) {
	if (c == 'L') return {-1, 0};
	if (c == 'R') return {1, 0};
	if (c == 'U') return {0, 1};
	return {0, -1};
}
bool check(int x, int y) {
	return 1 <= x && x <= h && 1 <= y && y <= w;
}
 
int id(char c) {
	if (c == 'L') return 0;
	if (c == 'R') return 1;
	if (c == 'U') return 2;
	return 3;
}
 
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> h >> w >> n;
	int x, y;
	cin >> x >> y;
	cin >> s + 1 >> t + 1;
	int sx = x, sy = y;
	rep(i, 1, n) {	
		if (s[i] == 'R') y++;
		if (!check(x, y)) cout << "NO", ioi
		if (t[i] == 'L' && y > 1) y--;
	}
	x = sx, y = sy;
	rep(i, 1, n) {	
		if (s[i] == 'L') y--;
		if (!check(x, y)) cout << "NO", ioi
		if (t[i] == 'R' && y < w) y++;
	}
	x = sx, y = sy;
	rep(i, 1, n) {	
		if (s[i] == 'U') x--;
		if (!check(x, y)) cout << "NO", ioi
		if (t[i] == 'D' && x < h) x++;
	}
	x = sx, y = sy;
	rep(i, 1, n) {	
		if (s[i] == 'D') x++;
		if (!check(x, y)) cout << "NO", ioi
		if (t[i] == 'U' && x > 1) x--;
	}
 
	cout << "YES";
	ioi
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")

#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) 
#define rep2(i, n, m) for (ll i = n; i <= (ll)(m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (ll)(m); --i)

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

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007;

int d[51][5001];

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, p; cin >> n >> p;
  vi a(n);

  rep(i, n) cin >> a[i];

  d[0][0] = 1;
  
  rep(i, n) rep(j, 5001) {
    if (j-a[i] >= 0) d[i+1][j] += d[i][j-a[i]];
    d[i+1][j] += d[i][j];
  }

  int ans = 0;
  rep(i, 5001) if (i % 2 == p) ans += d[n][i];

  cout << ans << endl;

  return (0);
}


Measured memory_bytes: 5508
import java.util.*;

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

    boolean tmp = true;

    while(tmp){
      long a = sc.nextLong();
      String op = sc.next();
      long b = sc.nextLong();

      if(op.equals("?")){
        tmp = false;
        break;
      } else if(op.equals("+")){
        System.out.println(a + b);
      } else if(op.equals("-")){
        System.out.println(a - b);
      } else if(op.equals("*")){
        System.out.println(a * b);
      } else {
        System.out.println(a / b);
      }
    }
  }
}



Measured memory_bytes: 26240
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
MOD = 10**9 + 7

class DisjointSet:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * n
        self.rank = [0] * n

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def has_same_root(self, x, y):
        return self.root(x) == self.root(y)

    def get_size(self, x):
        return self.size[self.root(x)]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x] 
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
n, m = map(int, input().split())
DS = DisjointSet(n)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    DS.unite(a, b)
ans = 0
for i in range(n):
    ans = max(ans, DS.get_size(i))
print(ans)

Measured memory_bytes: 90508
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    cout<< a*b/2 << endl;
    return 0;
}

Measured memory_bytes: 256