akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define M_PI 3.14159265358979323846

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 0};
int dy[]={0, 1, 0, -1, 0};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
 
std::string pad(int num){ char buffer[4]; std::snprintf(buffer, sizeof(buffer), "%03d", num); return buffer;}
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }


int main()
{
    fast_io();
    #ifdef __LOCAL
        fs::path p = __FILE__;
        fs::path input,output;
        input = output = p.parent_path();
        input += string("/input/") + string(p.stem()) + string(".txt");
        output += string("/output/") + string(p.stem()) + string(".txt");
        freopen(input.c_str(), "r", stdin);
        freopen(output.c_str(), "w", stdout);
    #endif
    int N;
    string S;
    cin >> N >> S;
    int ans=0;
    FOR(i,0,N){
        DBG(S.substr(i,3));
        if(S.substr(i,3)=="ABC"){
            ans++;
            }
        }
    cout << ans << endl;
}


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

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

const ll mod = 1000000007;

int main() {
    string s;
    cin >> s;
    rep(i,3) {
        if (s[i] == s[i+1]) {
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
    return 0;
}

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

int main ()
{
	long long h, w;
  	cin >> h >> w;
  	if (h % 2 == 0)
    {
    	cout << h * w / 2 << endl;
    }
  	else if (h % 2 == 1 && h != 1)
    {
    	if(w % 2 == 0)
        {
        	cout << ((h / 2) * w) + w / 2 << endl; 
        }
      	else if(w % 2 == 1 && w != 1)
        {
        	cout << ((h / 2) * w) + (w / 2) + 1 << endl;
        }
      	else if(w == 1)
        {
        	cout << 1 << endl;
        }
    }
  	else if (h == 1)
    {
    	cout << 1 << endl;
    }
}


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

int main() {
  int N;
  cin >> N;
  int a = N / 1000;
  int b = (N - 1000 * a ) / 100;
  int c = (N - 1000 * a - 100 * b ) / 10;
  int d = (N - 1000 * a - 100 * b - 10 * c );

  if ( b != c) {
    cout << "No" << endl;
  }
  else if ( a == b || c == d ) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * y / gcd(x, y); }

long mod = 10^^9 + 7;
//long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto A = RD;
	auto B = RD;

	writeln(A+B >= 10 ? "error" : (A+B).to!string);
	stdout.flush();
	debug readln();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long int64;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long  INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;
const int MAX_NUM = 999999999;
void solve() {
	string s; cin >> s;
	if (s[0] == '1') s[0] = '9';
	else if (s[0] == '9') s[0] = '1';
	if (s[1] == '1') s[1] = '9';
	else if (s[1] == '9') s[1] = '1';
	if (s[2] == '1') s[2] = '9';
	else if (s[2] == '9') s[2] = '1';
	cout << s << endl;
	return;
}
int main() {
	solve();
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>

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

using namespace std;

int n, m;

int main() {
    cin >> n >> m;
    int ans = (n - 1) * (m - 1);
    cout << ans << endl;
}


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

template <typename Weight, int MAX_N, Weight INF> class MaxFlow{
private:
	struct E{
		int to, rev;
		Weight lim;
		E(int x, Weight y, int z){
			to = x;
			lim = y;
			rev = z;
		}
	};

	vector<E> edge[MAX_N];
	int lev[MAX_N];
	int iter[MAX_N];


	Weight dfs(int s, int g, Weight f){
		if(s == g)return f;
		for(int &i = iter[s];i < edge[s].size();i++){
			E &e = edge[s][i];
				if(lev[e.to] <= lev[s] || e.lim <= 0)continue;
			Weight tmp = dfs(e.to, g, min(f, e.lim));
			if(tmp<1e-9)continue;
			e.lim -= tmp;
			edge[e.to][e.rev].lim += tmp;
			return tmp;
		}
		return 0;
	}

	void bfs(int x){
		queue<int> q;
		q.push(x);
		int p = 0;
			while(!q.empty()){
			for(int i = q.size();i--;){
				int tmp = q.front();q.pop();
				if(lev[tmp] != INF)continue;
				lev[tmp] = p;
				for(int j = 0;j < edge[tmp].size();j++){
					if(edge[tmp][j].lim > 0 && lev[edge[tmp][j].to] == INF)q.push(edge[tmp][j].to);
				}
			}
			p++;
		}
	}

public:
	void make_edge(int a, int b, Weight l){
		edge[a].push_back(E(b, l, edge[b].size()));
		edge[b].push_back(E(a, 0, edge[a].size() - 1));
	}

	Weight max_flow(int s, int g){
		Weight res = 0;
		bool fin = false;
		while(!fin){
			fill(lev, lev + MAX_N, INF);
			fill(iter, iter + MAX_N, 0);
			bfs(s);
			fin = true;
			while(true){
				Weight p = dfs(s, g, INF);
				if(p < 1e-9)break;
				fin = false;
				res += p;
			}
		}	
		return res;
	}
};


#define INF (1 << 30)

int dist[108][108];
int p[1080], t[1080];
int main(){
	int n, m, l, u, v, d;
	while(cin >> n >> m >> l, n|m|l){		
		MaxFlow<int, 2160, INF> mf;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				if(i == j)dist[i][j] = 0;
				else dist[i][j] = INF-1;
			}
		}
		for(int i = 0;i < m;i++){
			cin >> u >> v >> d;
			dist[u][v] = d;
			dist[v][u] = d;
		}
		for(int i = 0;i < n;i++)
			for(int j = 0;j < n;j++)
				for(int k = 0;k < n;k++)
					dist[j][k] = min(dist[j][i] + dist[i][k], dist[j][k]);
		for(int i = 0;i < l ;i++){
			cin >> p[i] >> t[i];
		}
		for(int i = 0;i < l;i++){
			mf.make_edge(l * 2, i, 1);
			mf.make_edge(i + l, l * 2+1, 1);			
			for(int j = 0;j < l;j++){
				if(i == j)continue;
				if(t[i] + dist[p[i]][p[j]] <= t[j]){
					mf.make_edge(i, j + l, 1);
				}
			}
		}
		cout << l - mf.max_flow(l * 2, l * 2 + 1) << endl;
	}
	return 0;
}

Measured memory_bytes: 18956
# ABC109D - Make Them Even
import sys
input = sys.stdin.readline


def main():
    H, W = tuple(map(int, input().rstrip().split()))
    A = list(
        list(map(lambda x: int(x) % 2, input().rstrip().split())) for _ in range(H)
    )
    ans = []
    # move left to right
    for i in range(H):
        for j in range(W - 1):
            if A[i][j]:
                A[i][j] ^= 1
                A[i][j + 1] ^= 1
                ans += [(i + 1, j + 1, i + 1, j + 2)]
    # move up to down
    for i in range(H - 1):
        if A[i][W - 1]:
            A[i][W - 1] ^= 1
            A[i + 1][W - 1] ^= 1
            ans += [(i + 1, W, i + 2, W)]
    print(len(ans))
    for i in ans:
        print(*i)


if __name__ == "__main__":
    main()

Measured memory_bytes: 26712
//7-C

import java.util.Scanner;

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

        int n = sc.nextInt();
        int m = sc.nextInt();
        int l = sc.nextInt();
        
        int[][] A = new int[n][m];
        int[][] B = new int[m][l];
        long[][] C = new long[n][l];
        
        //Aの配列に整数入力
        for(int i = 0 ; i < n ; i++ ){
        	for( int j = 0 ; j < m ; j++ ){
        		A[i][j] = sc.nextInt();
        	}
        }
        
        //Bの配列に整数入力
        for(int i = 0 ; i < m ; i++ ){
        	for( int j = 0 ; j < l ; j++ ){
        		B[i][j] = sc.nextInt();
        	}
        }
        
        //Cの配列に整数入力
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < l; j++) {
                for (int k = 0; k < m; k++) {
                    C[i][j] += A[i][k]*B[k][j];
                }
            }
        }
        
        //Cの中身出力
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < l; j++) {
            	
            	if(j == 0 ){
            		System.out.print(C[i][j]);
            	}else{
            		System.out.print(" " + C[i][j]);
            	}
            	
            }
            System.out.println();
        }
    }
}

Measured memory_bytes: 54288
#include<bits/stdc++.h>
using namespace std;
signed main(){
	int a;
	cin>>a;
	if(a<10){
		cout<<a<<endl;
	}
	else if(a<100){
		cout<<9<<endl;
	}
	else if(a<1000){
		cout<<(a-99)+9<<endl;
	}
	else if(a<10000){
		cout<<909<<endl;
	}
	else if(a<100000){
		cout<<(a-9999)+909<<endl;
	}
	else cout<<90909<<endl;
}


Measured memory_bytes: 256
n = gets.to_s.to_i
a = gets.to_s.split.map{|t| t.to_i }

if n == 0 && a[0] == 1
  puts 1
  exit
elsif a[0] == 1 || n == 0
  puts -1
  exit
end

remain_folia = a.sum 

k = 1
ans = 1
a.shift
a.each_with_index do |t, i|
  remain_folia -= t
  k = [k * 2 - t, remain_folia].min
  if k < 0 || ( k == 0 && i < n - 1 )
    puts -1
    exit
  end
  ans += k + t
  # p [k, t, remain_folia]
end

puts ans

Measured memory_bytes: 20816
#include"iostream"
#include <algorithm>

using namespace std;
int main()
{
	long long int n, k, h[100000], sum = 1000000000, hw[100000];
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	sort(h, h + n);

	for (int i = 0; i < n - (k - 1); i++) {
		hw[i] = h[i + (k - 1)] - h[i];
		if (sum > hw[i])sum = hw[i];
	}
	cout << sum << endl;
    return 0;
}


Measured memory_bytes: 1024
import math


def prime(M):
    if M == 1:
        return [1]
    lst = []
    for i in range(1, int(math.sqrt(M)+1)):
        if M % i == 0:
            lst.append(i)
            div = M // i
            if div not in lst:
                lst.append(div)
    return sorted(lst)


N, M = map(int, input().split())
lst = prime(M)
res = 1
for num in lst:
    if (M // N) < num:
        break
    else:
        res = num

print(res)


Measured memory_bytes: 3188
import java.util.Scanner;

class Main{
    public static void main(String[] args){
	int i;
	int j;
	int minj;
	int v;
	int count = 0;
	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();
	int A[] = new int[n];

	//Initialize data
        for(i=0 ; i<n ; i++){
            int num = scan.nextInt();
            A[i] = num;
        }
	
	for(i=0 ; i<n ; i++){
	    minj = i;
	    
	    for(j=i ; j<n ; j++){
		if(A[j] < A[minj]){
		    minj = j;
			}
	    }
	    if(A[i] != A[minj]){
	    	v = A[i];
	    	A[i] = A[minj];
	   		A[minj] = v;
	    	count++;
		}	
	}

	for(i=0 ; i<n-1 ; i++){
	    System.out.print(A[i] + " ");
	}
	System.out.println(A[i]);
	System.out.println(count);
	
    }
}



Measured memory_bytes: 26284
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    //*
    int a, b;
    cin >> a >> b ;
    //*/
    
    /*
    vector<int> a(3);
    cin >> a.at(0) >> a.at(1) >> a.at(2) ;
    
    sort(a.begin(), a.end());
    */
    
    //*
    if( a % 3 == 0 || b % 3 == 0 || ( a + b ) % 3 == 0  ){
        cout << "Possible" << endl;
    } else {
        cout << "Impossible" << endl;
    }
    //*/
    
    //cout << a.at(0) + a.at(1) << endl;

    return 0; 
}


Measured memory_bytes: 3616
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
// variadic template
template<typename T> inline void chmax(T &a, T b) { if (a < b) a = b; return; }
template<typename T> inline void chmin(T &a, T b) { if (a > b) a = b; return; }

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

  int a, b; cin >> a >> b;
  if (a <= 5) {
    print(0);
  } else if (a >= 13) {
    print(b);
  } else {
    print(b / 2);
  }

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <map>
const int MOD = 1e9+7;
#define PI 3.14159265359
typedef long long ll;
using namespace std;

ll par[100001];
ll ran[100001];
ll siz[100001];
vector<int> id[100001];
vector<int> num[100001];
 
void init(int n){
	for (int i = 0; i <= n; i++){
		par[i] = i;
		ran[i] = 0;
		siz[i] = 1;
	}
}
int find(int x){
	if (par[x] == x){
		return x;
	}else{
		par[x] = find(par[x]);
		return par[x];
	}
}
void unite(int x, int y){
	x = find(x);
	y = find(y);
	if (x == y) return;
 
	if (ran[x] < ran[y]){
		par[x] = y;
		siz[y] += siz[x];
	}else{
		par[y] = x;
		siz[x] += siz[y];
		if (ran[x] == ran[y]) ran[x]++;
	}
}
bool same(int x, int y){
	return find(x) == find(y);
}
int size(int x){
	return siz[find(x)];
}

int main(){
	int n, m;
	cin >> n >> m;
	init(n);
	vector<int> p(n+1);
	vector<pair<int, int> > vec(m);
	for (int i = 1; i <= n; i++){
		cin >> p[i];
	}
	for (int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		unite(x, y);
	}
	for (int i = 1; i <= n; i++){
		id[find(i)].push_back(i);
		num[find(i)].push_back(p[i]);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){
		if (id[i].size()){
			sort(num[i].begin(), num[i].end());
			int coun = 0;
			for (auto x : id[i]){
				coun += binary_search(num[i].begin(), num[i].end(), x);
			}
			ans += coun;
		}
	}
	cout << ans << endl;
	return 0;
}

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0
//

ll gcd( ll a, ll b ){
    if( a < b ) swap(b,a);
    ll c;
    while( a%b ){
        c = b;
        b = a%b;
        a = c;
    }
    return b;
}

int main() {

    int K;
    Scd(K);
    ll ans = 0;
    Rep(a,K) Rep(b,K) Rep(c,K){
        ans += gcd( gcd(a+1, b+1), c+1 );
    }

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

    return 0;
}



Measured memory_bytes: 3828
#include <iostream>
#include <vector>
#include <deque>

using namespace std;



int main(){
	int N, M, K;
	while(cin >> N >> M >> K){
		vector<long long> A(N);
		for(auto& t : A) cin >> t;
		auto dp = A;
		for(int i=2;i<=K;i++){
			deque<pair<int, long long>> qu;
			for(int j=0;j<N;j++){
				long long cur = 0;
				if(!qu.empty()) cur = qu.front().second;
				if(!qu.empty() && qu.front().first + M == j) qu.pop_front();
				while(!qu.empty() && qu.back().second <= dp[j]) qu.pop_back();
				qu.emplace_back(j, dp[j]);
				if(cur > 0) cur += i * A[j];
				dp[j] = cur;
			}
		}
		long long res = 0;
		for(auto& t : dp) res = max(res, t);
		cout << res << endl;
	}
}


Measured memory_bytes: 1792
h,w=map(int,input().split())
ans=[]
import sys
def s(a,b):
    for i in range(a):
        s=a*b
        x=i*b
        y=((a-i)//2)*b
        z=s-x-y

        d=(a-i)*(b//2)
        e=s-x-d
        ma=max(x,y,z)
        mi=min(x,y,z)
        mc=max(x,e,d)
        mn=min(x,e,d)
        res=min((ma-mi),(mc-mn))
        ans.append(res)
    return min(ans)
        
f=s(h,w)
g=s(w,h)
print(min(f,g))
    
# print(ans)
# print(min(ans))
    


Measured memory_bytes: 11032
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  string s; cin >> s;
  map<char, vector<int>> mp;
  rep(i, n) {
    mp[s[i]].push_back(i);
  }
  int ans = 0;
  auto dfs = [&](auto dfs, int pos, int cur) {
    if(cur == 3) {
      ans++;
      return;
    }
    rep(i, 10) {
      char c = '0'+i;
      auto ret = upper_bound(all(mp[c]), pos);
      if(ret == mp[c].end()) continue;
      dfs(dfs, *ret, cur+1);
    }
  };
  dfs(dfs, -1, 0);
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 3768
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N,M,Q; cin>>N>>M>>Q;
  vii dp(N,vi(N));
  rep(i,0,M){
    int L,R; cin>>L>>R;
    dp[L-1][R-1]++;
  }
  rep(i,0,N){
    REP(j,2,N) dp[N-j][i]+=dp[N-j+1][i];
  }
  rep(i,0,N){
    rep(j,1,N) dp[i][j]+=dp[i][j-1];
  }
  rep(i,0,Q){
    int L,R; cin>>L>>R;
    cout<<dp[L-1][R-1]<<endl;
  }
  }


Measured memory_bytes: 2944
import java.util.Scanner;

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

		new A1130().ans(sc);
	}

}

class Code {

}

class A1130 {

	int[] xdis = { -1, 0, +1, 0 };
	int[] ydis = { 0, -1, 0, +1 };

	int[][] cm;

	public void ans(Scanner sc) {
		while (true) {
			String str = sc.nextLine();
			String[] cut = str.split(" ");
			int W = Integer.parseInt(cut[0], 10);
			int H = Integer.parseInt(cut[1], 10);

			if (W == 0) {
				break;
			}

			cm = new int[H][W];

			int x = 0;
			int y = 0;
			for (int h = 0; h < H; h++) {
				String map = sc.nextLine();
				for (int w = 0; w < W; w++) {
					char c = map.charAt(w);
					switch (c) {
					case '.':
						cm[h][w] = 0;
						break;
					case '@':
						x = w;
						y = h;
						cm[h][w] = 0;
						break;
					case '#':
						cm[h][w] = -1;
						break;
					}
				}
			}
			rec(x, y);


			int count=0;
			for (int h = 0; h < H; h++) {
				for (int w = 0; w < W; w++) {
					if(cm[h][w]==1){
						count++;
					}
				}
			}
			System.out.println(count);

		}
	}

	void rec(int x, int y) {
		if (y < 0 || cm.length <= y) {
			return;
		}
		if (x < 0 || cm[0].length <= x) {
			return;
		}
		if (cm[y][x] != 0) {
			return;
		}

		cm[y][x] = 1;
		for (int i = 0; i < xdis.length; i++) {
			rec(x + xdis[i], y + ydis[i]);
		}
	}
}

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

using namespace std;

int abs(int x) {
  if(x < 0) {
    return (-1) * x;
  }
  else {
    return x;
  }
}

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

  if(abs(c - a) <= d) {
    cout << "Yes" << endl;
  }
  else if(abs(b - a) <= d && abs(c - b) <= d) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
import itertools
import numpy as np
N,D = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
count=0
for i in itertools.combinations(X,2):
  if np.linalg.norm(list(map(lambda x,y:abs(x-y),i[0],i[1])))%1==0:count+=1
print(count)

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

struct UnionFind {
	vector<ll> d;
	UnionFind(int n): d(n, -1){};

	// find
	ll find(int x) {
		if (d[x] < 0) return x;

		return d[x] = find(d[x]);
	}	

	int unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return false;
		}

		if (d[x] > d[y]) {
			swap(x, y);
		}

		d[x] += d[y];
		d[y] = x;

		return true;
	}

	// same
	bool same(int x, int y) {
		if (find(x) == -1 && find(y) == -1) {
			return false;
		}
		return (find(x) == find(y));
	}

	// size
	ll size(int x) {
		return abs(d[find(x)]);
	}





};

int main() {

	int N, M;

	cin >> N >> M;

	vector<int> A;
	vector<int> B;
	for (int i =0;i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		A.push_back(a);
		B.push_back(b);
	}

	ll inconv = (ll)N * (N-1)/2;
	
	UnionFind uf = UnionFind(N);
	vector<ll> ans;
	for (int i = M-1; i >=0; i--) {
		int a, b;
		a = A[i];
		b = B[i];

		ans.push_back(inconv);
		// 同じグループであれば無視
		if (!uf.same(a, b)) { 
			inconv -= (ll)uf.size(a) * uf.size(b);
		}
		uf.unite(a, b);
	}

	for (auto i = ans.rbegin(); i != ans.rend(); i++) {
		cout << *i << endl;
	}

	return 0;
}

Measured memory_bytes: 5872
/* Akshat Sharma @akshat98 */
#include <iostream>
#include <bits/stdc++.h>
#define IOS  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mp   make_pair
#define pb   push_back
#define F    first
#define S    second
#define ll   long long
#define MOD  1000000007
#define MAX  1000000001
#define vi   vector<int>
#define vl   vector<ll>
#define vpi  vector<pair<int,int> >
#define vpl  vector<pair<ll,ll> >
#define rep(i,a,b) for(i=a;i<b;i++)
#define reqp(i,a,b) for(i=a;i<=b;i++)
#define ren for(i=0;i<n;i++)
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;


int main()
{
	#ifndef ONLINE_JUDGE
	// freopen("input_file.txt", "r", stdin);
	//freopen("output_file.txt", "w", stdout);
	#endif
	int i,j,k,l,n,test_case,m,r;
	test_case=1;
	//cin>>test_case;
	while(test_case--){
		cin>>l>>r;
		if(r-l>=2019){
			cout<<"0\n";
		}else{
			l=l%2019;
			r=r%2019;
			if(l>=r){
				cout<<"0\n";
			}else{
				int ans=INT_MAX;
				reqp(i,l,r){
					reqp(j,i+1,r){
						ans=min(ans,(i*j)%2019);
					}
				}
				cout<<ans<<"\n";
			}
		}


	}
	
	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
a = list(map(int, input().split()))
par = list(range(N))

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        par[y] = x

for _ in range(M):
    unite(*map(int, input().split()))

group = {i: [] for i in range(N)}
for i in range(N):
    group[root(i)].append((a[i], i))
ans = 0
cnt = 2 * (N - M - 1)
if N < cnt:
    print('Impossible')
    exit()
elif cnt == 0:
    print(0)
    exit()

visited = set()
for g in group.values():
    if g:
        c, i = min(g)
        ans += c
        cnt -= 1
        visited.add(i)

for v, i in sorted((v, i) for i, v in enumerate(a)):
    if cnt > 0 and i not in visited:
        ans += v
        visited.add(i)
        cnt -= 1
print(ans)

Measured memory_bytes: 129976
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;
  while(cin>>n){
    if(n==0) return 0;
    
    vector<int> A(n+1);
    rep(i,n) cin>>A[i+1];
    
    int dp[310][310];
    rep(i,310){
      rep(j,310) dp[i][j]=0;
    }
    
    for(int i=1;i<n;i++){
      if(abs(A[i]-A[i+1])<=1){
        dp[i][i+1]=2;
      }
    }
    
    for(int l=3;l<=n;l++){
      for(int i=1;i+l-1<=n;i++){
        int j=i+l-1;
        if(dp[i+1][j-1]==j-i-1 && abs(A[i]-A[j])<=1) dp[i][j]=j-i+1;
        for(int k=i;k<j;k++){
          dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
        }
      }
    }
    cout<<dp[1][n]<<endl;
  }
    
  return 0;
}


Measured memory_bytes: 3464
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
n, m, x, y = M()
xlist = LI()
ylist = LI()
ans = 'War'
for i in range(-100, 101):
    if x < i and y >= i and max(xlist) < i and min(ylist) >= i:
        ans = 'No War'
        break
print(ans)

Measured memory_bytes: 68572
#include <stdio.h>

const int Mod = 998244353;

int main()
{
	int N;
	char S[2001];
	scanf("%s", S);
	for (N = 0; S[N] != 0; N++);
	
	int i, j, l = 0, r = 0, tmp[2] = {};
	long long dp[4001] = {1};
	for (i = 0; i < N; i++) {
		if (S[i] == '0') tmp[0] += 2;
		else if (S[i] == '2') tmp[1] += 2;
		else {
			tmp[0]++;
			tmp[1]++;
		}
		if (r < tmp[0]) r++;
		for (j = r; j > l; j--) dp[j] = (dp[j] + dp[j-1]) % Mod;
		if (l + tmp[1] <= i) dp[l++] = 0;
	}
	for (; i < N * 2; i++) {
		if (r < tmp[0]) r++;
		for (j = r; j > l; j--) dp[j] = (dp[j] + dp[j-1]) % Mod;
		if (l + tmp[1] <= i) dp[l++] = 0;
	}
	printf("%lld\n", dp[r]);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 1736
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <iostream>
#include <vector>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
typedef long long ll;

int main(void) {
  int a, b, c;
  cin >> a >> b >> c;
  cout << min(c, b/a) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<list>
#include<iterator>
#include<vector>
#include<algorithm>

using namespace std; 

typedef long long int ll;
typedef long unsigned lu;
typedef vector<ll> v;
typedef pair<ll,ll> p;
typedef vector <p> vp;
#define rep(i,j,k) for(ll i=j;i<k;i++)
#define repr(i,j,k) for(ll i=k;i>=j;i--)
#define read(a,n) rep(i,0,n) cin>>a[i];
#define show(a,n) rep(i,0,n) cout<<a[i]<<" ";
#define ipair pair <int,int>
#define mp make_pair 
#define pb push_back 
#define modulus 1000000007
#define MAX 100005
#define INF 1000000001
// #define cinv vl a(n) rep(i,0,n) { cin>>a[i]; }
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL);
ll x[300005]={0};
ll y[300005]={0};
// char dp[1000][1000];

int main()
{
    fastio();
    string s;
    cin>>s;
    int n=s.size();
    int max=0;
    int count=0;
    int i=0;
    while(i<n)
    {
        if(s[i]=='R')
        {
            count=0;
            while(s[i]=='R')
            {
                i++;
                count++;
            }
            if(count>max)
            {
            max=count;
            }
        }
        i++;
    }
    cout<<max<<"\n";
}



Measured memory_bytes: 3628
N=int(input())
S=input()

ans=S.count("R")*S.count("G")*S.count("B")

#j-i= k-j k=2*j-i

for i in range(N):
  for j in range(i+1,N):
    if 2*j-i<N:
      if S[i]!=S[j] and S[i]!=S[2*j-i] and S[j]!=S[2*j-i]:
        ans -=1
        
print(ans)
      
    
    

Measured memory_bytes: 9152
import sys
import itertools
 
 
def check(i,array):
    now=0
    while True:
        flag=0
        if(now==len(i)-1):
            return 1
        for x in array:
            if(i[now]==x[0] and i[now+1]==x[1] or \
                i[now]==x[1] and i[now+1]==x[0]):
 
                flag=1
                now+=1
                break
 
        if(flag==0):
            return 0
 
 
def main():
    N, M = map(int,input().split())
 
    array=[]
    sum=0
 
    for _ in range(0, M):
        array.append(list(map(int,input().split())))
 
 
    for i in itertools.permutations(range(1,N+1),N):
        if(i[0]==1):
            sum += check(i,array)
    print(sum)
 
main()

Measured memory_bytes: 3064
# 02
import sys
import math


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, m = LI()
s = S()
t = S()

gcd = math.gcd(n, m)
lcm = n * m // gcd
i_s = n // gcd
i_t = m // gcd
for i in range(gcd):
    if s[i*i_s] != t[i*i_t]:
        print(-1)
        exit()
print(lcm)


Measured memory_bytes: 9248
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll INF=mod*mod;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(x) (x).begin(),(x).end()
ll min(ll a,ll b){
  if(a>b){
    return b;
    }
      else{
        return a;
      }
  }
  
  ll max(ll a,ll b){
    if(a>b){
      return a;
    }
    else{
      return b;
    }
  }

ll power(ll a,ll b){
 ll ans=1;
 for(ll i=1;i<=b;i++){
ans*=a;
  }
  return ans;
}

 ll gcd(ll m,ll n){
 	if(n==0){
       return m;
     }
   return gcd(n,m%n);
 }
ll lcm(ll a,ll b){
  ll g=gcd(a,b);
  return a/gcd(a,b)*b;
		

}
int main(){
  
  string S;
  cin>>S;
  
  if(S=="SUN"){
    cout<<7<<endl;
  }
  else if(S=="MON"){
    cout<<6<<endl;
  }
else if(S=="TUE"){
cout<<5<<endl;
}
else if(S=="WED"){
cout<<4<<endl;
}
else if(S=="THU"){
cout<<3<<endl;
}
else if(S=="FRI"){
cout<<2<<endl;
}
else if(S=="SAT"){
cout<<1<<endl;
}
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main () {
    int a, b, c, x, y, mn, ans = 0;
    cin >> a >> b >> c >> x >> y;
    mn = min(x, y);
    if(a > 2 * c)
        a = 2 * c;
    if(b > 2 * c)
        b = 2 * c;
    if(a + b > 2 * c)
        ans = mn * 2 * c, x -= mn, y -= mn;
    ans = ans + x * a + y * b;
    cout << ans << endl;
    return 0;
}


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

signed main() {
    vector<int> a(3);
    cin >> a;
    sort(ALL(a));
    int mn = a[0];
    REP(i, 3) a[i] -= mn;
    int ans = 0;
    if (a[1] % 2) {
        ans = (a[1] + 1) / 2;
        ans += a[2] - a[1];
        ans ++; 
    } else {
        ans = a[1] / 2;
        ans += (a[2] - a[1]);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
using namespace std::chrono; 

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
#define db cout << " HERE " << endl;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 200001;
int adp[1002][1002];
int main() {
	int n , m ;
	cin >> n >> m ;
	int dp[n][m];
	dp[0][0]=1;
	int ar[n][m];
	F0R(i,n) {
		string k ;
		cin >> k;
		F0R(j,m) {
			ar[i][j] = k[j];
			dp[i][j]=0;
		}
	}
	if(ar[0][0]=='#') dp[0][0]=0;
	else dp[0][0]=1;
	F0R(i,n) {
		F0R(j,m) {
			if(i==0 and j==0) continue;
			if(i==0 and ar[i][j]!='#') dp[i][j]=(dp[i][j]%MOD+ dp[i][j-1]%MOD)%MOD;
			else if(j==0 and ar[i][j]!='#') dp[i][j]=(dp[i-1][j]%MOD + dp[i][j]%MOD)%MOD;
			else if(ar[i][j]!='#') dp[i][j]=(dp[i-1][j]%MOD+dp[i][j-1]%MOD + dp[i][j]%MOD)%MOD;
			else dp[i][j] = 0;
		}
	}
	cout << dp[n-1][m-1];
}
			
		
// template by benq


Measured memory_bytes: 11408
using System;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.Linq;
using System.Reflection;
using System.Runtime.InteropServices;
using System.Runtime.Serialization;
using System.Security.Cryptography.X509Certificates;
using System.Xml;

namespace hello_world
{
	class Program
	{

		static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			string[] aa = Console.ReadLine().Split(" ");
			ulong[] a = new ulong[n];
			ulong sum = 1;
			for (int i = 0; i < n; i++)
				Input1(aa[i], out a[i]); 

			if (aa.Contains("0"))
				Console.WriteLine("0");
			else
			{
				try
				{
					checked
					{
						for (int i = 0; i < n; i++)
						{
							sum *= a[i];
						}
						if (sum > 1000000000000000000)
							Console.WriteLine("-1");
						else
							Console.WriteLine(sum);
					}
				}

				catch (OverflowException ex)
				{
					Console.WriteLine("-1");
				}
			}
		}
		private static ulong Input1(string s,out ulong n) 
		{
			if (ulong.TryParse(s, out n))
					n = ulong.Parse(s);
			else
				n = 0;
			return n; 
		}
		
	}
	 
}




Measured memory_bytes: 41736
#include <bits/stdc++.h>
using namespace std ;
int a,b,x,y;
int main(){
	string a,b,c;
	cin>>a;
	cin>>b;
	cin>>x>>y;
	cin>>c;
	
	if(a[0]==c[0]){
		cout<<x-1<<" "<<y;
	}
	else{
		cout<<x<<" "<<y-1;
	}
	cout<<endl;
}

Measured memory_bytes: 768
//Name-Deepesh Bhatt
//Institute-IIT Dhanbad

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

ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll lcm(ll a ,ll b)
{
    return a/gcd(a,b)*b;
}
ll power(ll a, ll n, ll m)
{
    if (n == 0)
        return 1;
    ll p = power(a, n / 2, m);
    p = (p * p) % m;
    if (n % 2)
        return (p * a) % m;
    else
        return p;
}
int main()
{
    ios_base::sync_with_stdio(false);    //for fast I/O operation
    cin.tie(NULL);
    ll t;
    t=1;
    while(t--) {
        string s;
        cin>>s;
        int l=s.length();
        int flag=0;
        for(int i=0;i<l;i++)
        {
            if(s[i]!=s[l-i-1])
            {
                flag++;
                break;
            }
        }
            int count=0;
            int k=(l-1)/2;
            for(int i=0;i<k;i++)
            {
                if(s[i]!=s[k-1-i])
                {
                    count++;
                    break;
                }
            }
            k=(l+3)/2;
            int count2=0;
            for(int i=k;i<l;i++)
            {
                if(s[i]!=s[l-1-i])
                {
                    count2++;
                    break;
                }
            }
            if(flag==0&&count==0&&count2==0)
                cout<<"Yes";
            else cout<<"No";
    }
    return 0;
}

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

int		main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int x = 1;
	int n, k;
	cin >> n >> k;
	rep(i, n) {
		if (x * 2 < x + k)
			x *= 2;
		else
			x += k;
	}
	cout << x << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;


int main()
{
	ll n,k;
	cin >> n >> k;
	ll ans = 0;
	for(ll i = k;i<=n+1;i++)
	{
		(ans+= (n-i+1)*i+1+MOD)%=MOD;
		//cout<<ans<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n;
    cin >> n;
    if (n&1) {
        cout << 0 << endl;
        return 0;
    }
    ll ans = 0;
    for (int i = 1; (ll)pow(5, i) * 2 <= n; ++i) {
        ll x = (ll)pow(5, i) * 2;
        ans += n/x;
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define lim 1000000000000000007
#define lim1 18446744073709551615  //Unsigned
#define sq(a) ((a)*(a))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mms(v,i) memset(v,i,sizeof(v))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> PL;
typedef pair<ll,int> PLI;
typedef pair<int,ll> PIL;
typedef pair<int,pair<int,int> > pii;
typedef pair<double,double> pdd;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a,ll b,int m) {
    if (b==0) return 1;
    ll c = power(a,b>>1,m);
    c = (c*c)%m;
    if (b&1) return (c*a)%m;
    return c;
}
ll powerwithoutmod(ll a,ll b) {
    if (b==0) return 1;
    ll c = powerwithoutmod(a,b>>1);
    c = (c*c);
    if (b&1) return (c*a);
    return c;
}
ll gcdll(ll a,ll b) {
    if (b==0) return a;
    return gcdll(b,a%b);
}
int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = (int)1e5+5;
const int Q = 301;
const int logN = 16;

set<int> pos[26];
string s;
void solve() {
    int n,q,t,l,r;
    char ch;
    cin>>n;
    cin>>s;
    cin>>q;
    REP(i,1,n) {
        pos[s[i-1]-'a'].insert(i);
    }
    while (q--) {
        cin>>t>>l;
        if (t==1) {
            cin>>ch;
            r = ch-'a';
            pos[s[l-1]-'a'].erase(l);
            s[l-1] = ch;
            pos[r].insert(l);
        }
        else {
            cin>>r;
            int ans = 0;
            REP(i,0,25) {
                auto it = pos[i].lower_bound(l);
                if (it!=pos[i].end() && (*it)<=r) {
                    ans++;
                }
            }
            cout<<ans<<"\n";
        }
    }
}
int main() {
    //freopen("output.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T=1;
    //cin>>T;
    REP(TC,1,T) {
        //cout<<"Case #"<<TC<<": ";
        solve();
        //cout<<"\n";
    }
}


Measured memory_bytes: 24220
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;
int main(){
  Int l,r;cin >> l >> r;
  Int ans = INF;
  if(r-l>2020){cout << 0 << endl;return 0;}
  for(Int i=l;i<r;i++){
    for(Int j=i+1;j<=r;j++){
      ans=min(ans,i*j%2019);
    }
  }
  cout << ans << endl;
}


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

#define mem( arr, i ) fill( arr, arr + sizeof (arr), i )
#define MEM( arr, i ) memset( arr, i, sizeof (arr) )
#define Push push_back
#define Pair make_pair
typedef unsigned long long ull;
typedef long long lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vcI;
typedef vector<lli> vcL;
typedef vector<pii> vPI;
typedef vector<pll> vPL;
//typedef priority_queue<T> prior_S<T>;
//typedef priority_queue< T, vector<T>, greater<T> > prior_B<T>;
const double PI = 3.141592653589793;
const lli I_MAX = 1LL << 60;
const lli mod = 1000000007;

vcL color( 100000+99, 0 );
bool vis[ 100000+99 ];

void DFS(vPL *adj, int now) {
	for (auto x : adj[now]) {
		if ( vis[x.first] ) continue;
		else vis[x.first] = true;
		
		if ( x.second == 1 ) color[x.first] = !color[now];
		else color[x.first] = color[now];
		
		DFS( adj, x.first );
	}
}

void solve() {
	MEM( vis, false );
	
	lli n = 1;
	cin >> n;
	
	vPL adj[ n+1 ];
	
	for (int i = 0; i < n-1; ++i) {
		int from, to, dis;
		cin >> from >> to >> dis;
		adj[from].Push( Pair( to, dis%2 ) );
		adj[to].Push( Pair( from, dis%2 ) );
	}
	
	DFS( adj, 1 );
	
	for (int i = 1; i <= n; ++i) cout << color[i] << '\n';
}

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


Measured memory_bytes: 10112
import sys
input = sys.stdin.readline
import bisect
def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    cum_a = [0] * (N + 1)
    for i in range(N):
        cum_a[i+1] = cum_a[i] + A[i]
    cum_b = [0] * (M + 1)
    for i in range(M):
        cum_b[i+1] = cum_b[i] + B[i]
    ans = 0
    for i in range(N+1):
        rest = K - cum_a[i]
        if rest < 0:break
        b_idx = bisect.bisect_right(cum_b, rest)
        ans = max(ans, i + b_idx - 1)
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 118268
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n, k;
	cin >> n >> k;
	int *a = new int[n + 1];
	int *ans = new int[n + 1];
	int i, j, ii, jj;
	for (i = 0; i < n; i++) {
		cin >> a[i];
		ans[i] = 0;
	}
	bool allN;

	for (i = 0; i < k; i++) {
		for (j = 0; j < n; j++) {
			int limit = min(n - 1, j + a[j]);
			ii = max(0, j - a[j]);
			ans[ii]++;
			if (limit + 1 < n) {
				ans[limit + 1]--;
			}
		}

		allN = true;
		a[0] = ans[0];
		for (j = 1; j < n; j++) {
			a[j] = ans[j] = ans[j] + ans[j - 1];
			if (a[j] != n) {
				allN = false;
			}
			ans[j-1] = 0;
		}
		ans[n-1] = 0;
		if (allN == true)break;
	}

	cout << a[0];
	for (i = 1; i < n; i++) {
		cout << " " << a[i];
	}
	cout << endl;


	return 0;
}


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

#define y1 aklsdja
#define ii pair < int , int >
#define iii pair < int , ii >
#define iv pair < ii , ii >

#define fi first
#define se second
#define pb push_back
#define t top()
#define fr front()

#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , x) for(int i = 0 ; i < x ; ++i)
#define FORD(i , x , n) for(int i = x ; i >= n ; --i)

#define oo 1e17 + 5
#define ll long long
#define int long long
#define pow poww

const int N = 1e5 + 5;
int n , k;
int dp[N] , a[N];

main()
{
    //freopen("K.inp","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    FOR(i , 1 , n)
        cin >> a[i];
    FORD(i , k , 1)
        FOR(j , 1 , n)
            if(i + a[j] == k + 1 || (i + a[j] <= k && dp[i + a[j]] == 0))
                dp[i] = 1;
    if(dp[1] == 1)
        cout << "First";
    else
        cout << "Second";
}


Measured memory_bytes: 1024