akhauriyash/Code-Regression huggingface dataset:
n = int(input())
a = list(map(int, input().split()))
ans = sum(a)
al = ans
mod = 0
for i in range(n):
  if mod + a[i] == al - a[i]:
    ans = 0
    break
  elif ans > abs(mod - al + 2*a[i]):
    ans = abs(mod - al + 2*a[i])
    mod += a[i]
    al -= a[i]
  else:
    mod += a[i]
    al -= a[i]
print(ans)

Measured memory_bytes: 26060
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main{
    static long mod=1000000007;
//    static int dx[]={-1,0,1,0};
//    static int dy[]={0,-1,0,1};

    public  static void main(String[] args)   throws Exception, IOException{        
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);

        int n = sc.nextInt();
        int k = sc.nextInt();
        char c[]=sc.nextString().toCharArray();
        c[k-1]+=32;
        for (int i = 0; i < c.length; i++) {
			out.print(c[i]);
		}
        out.println();
        out.flush();
    }
    



    static boolean validpos(int x,int y,int r, int c){
        return x<r && 0<=x && y<c && 0<=y;
    }

    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }  
}

//class P {
//    int id, d;
//    P(int  id, int d) {
//        this.id=id;
//        this.d=d;
//    }
//}

//class P implements Comparable<P>{
//    int id,T;
//    P(int id, int T) {
//        this.id=id;
//        this.T=T;
//    }
//    public int compareTo(P p){
//        return id-p.id; //des
//    }
//}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public int[] nextIntArray(int size) throws IOException{
    	int r[] = new int[size];
    	for (int i = 0; i < size; i++) {
			r[i] = this.nextInt(); 
		}
    	return r;
    }
    public long[] nextLongArray(int size) throws IOException{
    	long r[] = new long[size];
    	for (int i = 0; i < size; i++) {
			r[i] = this.nextLong(); 
		}
    	return r;
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


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

#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define mod 1000000007
#define INF 2000000000
typedef long long ll;
bool compare(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}
// 入力



int main() {
    ll N,K,Q;
    ll add[100002]={};
    ll A[100002];
    cin >> N >>K>>Q;
    rep(i,Q){
        cin >> A[i];
    } 
    rep(i,Q){
        add[A[i]-1]++;
    }

    rep(i,N){
        if(add[i] > (Q-K)){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    
    return 0;
    

}

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

int a[105];

int main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;

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

    sort(a + 1, a + n + 1);

    int cnt = 0;
    for (int i = n; i >= n - m + 1; i--) {
        if (4 * m * a[i] >= sum) {
            cnt++;
        }
    }

    if (cnt == m) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int gcd(int x, int y) {
  if (x % y == 0) return y;
  return gcd(y, x % y);
}

int main() {
  long a, b;
  std::cin >> a >> b;
  std::cout << gcd(a, b) << std::endl;
  return 0;
}



Measured memory_bytes: 3112
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int b;
  int c;
} bcstruct;


int compare_long(const void *a, const void *b)
{
    return *(long*)a - *(long*)b;
}

int compare_bcstruct(const void *a, const void *b)
{
    return ((bcstruct*)a)->c - ((bcstruct*)b)->c;
}

int main()
{
  int n, m, b, c;
  int j,k;
  int ow;
  int ri;
  long num[100000];
  bcstruct bc[100000];
  scanf("%d %d",&n, &m);
  for(int i=0;i<n;i++) scanf("%ld",&num[i]);
  qsort(num, n, sizeof(long), compare_long);
  for(int i=0;i<m;i++) scanf("%d %d",&bc[i].b, &bc[i].c);
  qsort(bc, m, sizeof(bcstruct), compare_bcstruct);

//  for(int i=0; i<m; i++) printf("%d %d\n",bc[i].b,bc[i].c);
  
  long sum=0;
  int nump=n-1;
  int bcp=m-1;
  int counted=0;
  while(counted<n){
    //printf("sum:%d counted:%d nump:%d bcp:%d\n",sum,counted,nump,bcp);
    if(bcp<0 || num[nump]>=bc[bcp].c){
      sum+=num[nump];
      counted++;
      nump--;
      //printf("sum:%d counted:%d nump:%d\n",sum,counted,nump);
//      if(nump>0) this never happens.
    }else{
      if(bc[bcp].b <= n-counted){
        sum+= (long)bc[bcp].c * (long)bc[bcp].b;
        counted += bc[bcp].b;
        bcp--;
        //printf("sum:%d counted:%d bcp:%d\n",sum,counted,bcp);
      }else{
        sum+= (long)bc[bcp].c * (long)(n-counted);
        counted = n;
        //printf("sum:%d counted:%d bcp:%d\n",sum,counted,bcp);
      }
    }
  }
  printf("%ld\n",sum); 
  return 0;
}



Measured memory_bytes: 2548
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>
// 追加１
#include <fstream>
 
 
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
 
 
int main()
{
    string s;
    cin >> s;
 
    rep(i, s.size())
    {
        if (s[i] == '7')
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
 
    cout << "No" << endl;
    return 0;
}

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

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;
void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const ll INF = 1LL << 60;

//Write From this Line

int main()
{
	ll n ;
	cin >>  n ;
	ll x = 1 , y = n ;//x <= y で構成する
	for(ll i =1 ; i * i <= n ; i ++){
		if(n % i == 0){
			x = i ;
			y = n / i ;
		}
	}
	cout << (x-1) + (y-1) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n,x,t;
int main()
{
	cin >>n>>x>>t;
	cout <<(n+x-1)/x*t;
	return 0; 
}

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

int main(){
  	int K;
  	long sum=0;
  	cin >> K;
  	for(int i=1; i<=K; i++){
    	for(int j=1; j<=K; j++){
        	for(int k=1; k<=K; k++){
              	long num = gcd(j, k);
              	if(num==1){
                	sum+=1;
                }else{
            		sum+=gcd(i, num);
                }
            }
        }
    }
  	cout << sum << endl;
 	return 0;
}

Measured memory_bytes: 3180
import java.io.IOException;
import java.io.InputStream;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.NoSuchElementException;
 
public class Main {
	private static FastScanner sc = new FastScanner();
	static BigDecimal[] fact = new BigDecimal[51];
	
	public static void main(String[] args) {
		int N = sc.nextInt();
		int P = sc.nextInt();
		
		fact[0] = new BigDecimal(1);
		for(int i=1; i<fact.length; i++) {
			fact[(int)i] = fact[(int)i-1].multiply(new BigDecimal(i));
		}
		
		int even = 0;
		int odd = 0;
		for(int i=0; i<N; i++) {
			int a = sc.nextInt();
			if(a%2 == 0) {
				even++;
			} else {
				odd++;
			}
		}
		
		BigDecimal sum = new BigDecimal(0);
		if(P == 0) {
			for(int j=0; j<=odd; j+=2) {
				sum = sum.add(nck(odd, j));
			}
		} else {
			for(int j=1; j<=odd; j+=2) {
				sum = sum.add(nck(odd, j));
			}
		}
		
		for(int i=0; i<even; i++) {
			sum = sum.multiply(new BigDecimal(2));
		}
		
		System.out.println(sum.toPlainString());
	}
	
	static BigDecimal nck(int n, int k) {
		return fact[n].divide(fact[k], RoundingMode.HALF_UP).divide(fact[n-k], RoundingMode.HALF_UP);
	}
	
	static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}

Measured memory_bytes: 21332
#include <bits/stdc++.h>
using namespace std;
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 (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<28;
const long long MOD =1000000000+7;
int main(){
	int r,g,b,n;
	cin >>r>>g>>b>>n;
	long long ans=0;
	for(int a1=0;a1<=(n+r-1)/r;a1++){
		for (int a2 = 0; a2 <= (n-a1*r + g - 1) / g; a2++){
			if (a1 * r + a2 * g <= n and( n-a1 * r - a2 * g)%b==0 ){
				ans++;
			//	cout<<a1<<" "<<a2<<endl;
			}
		}
	}
	cout <<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
#define sz(v) ((int)(v).size())
using pi = pair<int, int>;
using lint = __int128;

const lint mod = 1e12L + 39;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x;
	while(p){
		if(p & 1) ret = ret * piv % mod;
		piv = piv * piv % mod;
		p >>= 1;
	}
	return ret;
}
vector<lint> berlekamp_massey(vector<lint> x){
	vector<lint> ls, cur;
	lint lf, ld;
	for(int i=0; i<x.size(); i++){
		lint t = 0;
		for(int j=0; j<cur.size(); j++){
			t = (t + (lint)x[i-j-1] * cur[j]) % mod;
		}
		if((t - x[i]) % mod == 0) continue;
		if(cur.empty()){
			cur.resize(i+1);
			lf = i;
			ld = (t - x[i]) % mod;
			continue;
		}
		lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
		vector<lint> c(i-lf-1);
		c.push_back(k);
		for(auto &j : ls) c.push_back(-j * k % mod);
		if(c.size() < cur.size()) c.resize(cur.size());
		for(int j=0; j<cur.size(); j++){
			c[j] = (c[j] + cur[j]) % mod;
		}
		if(i-lf+(int)ls.size()>=(int)cur.size()){
			tie(ls, lf, ld) = make_tuple(cur, i, (t - x[i]) % mod);
		}
		cur = c;
	}
	for(auto &i : cur) i = (i % mod + mod) % mod;
	return cur;
}

lint get_nth(vector<lint> rec, vector<lint> dp, lint n){
	int m = rec.size();
	vector<lint> s(m), t(m);
	s[0] = 1;
	if(m != 1) t[1] = 1;
	else t[0] = rec[0];
	auto mul = [&rec](vector<lint> v, vector<lint> w){
		int m = v.size();
		vector<lint> t(2 * m);
		for(int j=0; j<m; j++){
			for(int k=0; k<m; k++){
				t[j+k] += 1ll * v[j] * w[k] % mod;
				if(t[j+k] >= mod) t[j+k] -= mod;
			}
		}
		for(int j=2*m-1; j>=m; j--){
			for(int k=1; k<=m; k++){
				t[j-k] += 1ll * t[j] * rec[k-1] % mod;
				if(t[j-k] >= mod) t[j-k] -= mod;
			}
		}
		t.resize(m);
		return t;
	};
	while(n){
		if(n & 1) s = mul(s, t);
		t = mul(t, t);
		n >>= 1;
	}
	lint ret = 0;
	for(int i=0; i<m; i++) ret += 1ll * s[i] * dp[i] % mod;
	return ret % mod;
}
lint guess_nth_term(vector<lint> x, lint n){
	if(n < x.size()) return x[n];
	vector<lint> v = berlekamp_massey(x);
	if(v.empty()) return 0;
	return get_nth(v, x, n);
}

int f(string s){
	int ret = 0;
	for(int i=0; i<sz(s); ){
		int e = i;
		while(e < sz(s) && s[i] == s[e]) e++;
		ret += (e - i) / 2;
		i = e;
	}
	return ret;
}

int main(){
	int k; string s, t;
	cin >> s >> k;
	vector<lint> v = {0};
	for(int i=1; i<=100; i++){
		t += s;
		v.push_back(f(t));
	}
	cout << (long long)guess_nth_term(v, k) << endl; 
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
ll mod=1e9+7,num[100005];
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b/=2; 
    }
    return res%mod;
}
int main(){
    ll n,k,ans=0;
    cin>>n>>k;
    for(ll i=k;i>=1;i--){
        num[i]=qpow(k/i,n);
        for(ll j=i*2;j<=k;j+=i){
            num[i]=(num[i]-num[j]+mod)%mod;
        }
        ans=(ans%mod+num[i]%mod*i%mod)%mod;
    }
    cout<<ans%mod<<endl;
}

Measured memory_bytes: 4368
import sys
input = sys.stdin.readline

x, k, d = map(int, input().split())
tmp = abs(x) // d

if k < tmp:
  result = abs(abs(x) - d*k)
elif tmp%2 == k%2:
  result = abs(abs(x) - d*tmp)
else:
  a = result = abs(abs(x) - d*tmp)
  result = abs(abs(a) - d)

print(result)


Measured memory_bytes: 9164
// Problem : A - Password
// Contest : AtCoder Beginner Contest 140
// URL : https://atcoder.jp/contests/abc140/tasks/abc140_a
// Memory Limit : 1024,000000 MB 
// Time Limit : 2000,000000 milisec 
// Powered by CP Editor (https://github.com/coder3101/cp-editor2)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main() {
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

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

  cout.precision(16);
  cout << fixed;
  
  int n;
  cin >> n;
  
  cout << n * n * n;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
 int N,X,m[101];
 int souryou = 0, M = 1001001001;//なんで?100000とかじゃダメなん？
  cin >>N >>X;
  
 for(int i = 0; i < N; ++i){
 cin >> m[i];
 souryou += m[i];
 if(m[i] < M){
 M = m[i];
   } 
 }
 
  
 X = (X-souryou)/M +N;

 cout << X << endl;
 }

Measured memory_bytes: 256
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);

	//0505
	static class Questionnaire {
		void placeRank() {
			for(;;) {
				int n = Integer.parseInt(sc.next());
				int m = Integer.parseInt(sc.next());
				if(n==0 && m==0) break;

				HashMap<Integer, Integer> places = new HashMap<Integer, Integer>();
				for(int i=1; i<m+1; i++) {
					places.put(i, 0);
				}
				for(int i=0; i<n; i++) {
					for(int j=1; j<m+1; j++) {
						int check = Integer.parseInt(sc.next());
						places.put(j, places.get(j)+check);
					}
				}

				for(int i=0; i<m; i++) {
					int max=1;
					for(int j=2; j<m+1; j++) {
						if(places.get(max) < places.get(j)) max = j;
					}
					if(i != m-1)
						System.out.print(max + " ");
					else
						System.out.println(max);
					places.put(max, -1);
				}
			}
		}
	}

	public static void main(String[] args) {
		Questionnaire q = new Questionnaire();
		q.placeRank();
	}
}

Measured memory_bytes: 12000
import sys
s=input()
if("C" in s and "F" in s):
  for i in range(len(s)):
    if(s[i]=="C"):
      c=i
      break
  for i in range(len(s))[::-1]:
    if(s[i]=="F"):
      f=i
      break
  if(c<f):
    print("Yes")
    sys.exit()
print("No")


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

int main() {
  int n;cin>>n;
  ll an[n];rep(i,n)cin>>an[i];
  ll pn[n];rep(i,n) pn[i] = i - an[i] + 1;
  ll qn[n];rep(i,n) qn[i] = i + an[i] + 1;
  ll pdp[n];rep(i,n)pdp[i]=0;
  rep(i,n) if (pn[i] >= 0) {
    pdp[ pn[i] ] ++ ;
  }
  ll cnt=0;
  rep(i,n) if (qn[i] < n) {
    cnt += pdp[ qn[i] ];
  }
  cout<<cnt;
}


Measured memory_bytes: 9820
#include <stdio.h>
#include <stdbool.h>

int main()
{
    int a, b, c, i;
    bool flag = false;
    scanf("%d%d%d", &a, &b, &c);
    for (i=1; i<=b; i++)
    {
        if (a*i % b == c) {
            flag = true;
            break;
        }
    }
    if (flag) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
ll d[256];
int main() {
  ios::sync_with_stdio(false);
  int N;
  string S;
  cin >> N;
  cin >> S;
  for (int i=0; i<N; i++) {
    d[S[i]]++;
  }
  ll MOD = 1000000007LL;
  ll ret = 1;
  for (int i='a'; i<='z'; i++) {
    ret = (ret * (d[i] + 1LL)) % MOD;
  }
  ret--;
  cout << ret << endl;
}

Measured memory_bytes: 512
import math


S = input()
N = len(S)
cnt = 1

idxs_change = []
rl = []
for i in range(0,N-1):
    if S[i] == S[i+1]:
        cnt += 1
    else:
        idxs_change.append(i)
        rl.append(cnt)
        cnt = 1

rl.append(cnt)
ans = [0] * N
for i in range(math.ceil(len(rl) / 2)):
    idx = idxs_change[2*i]
    cnt = (rl[2*i] + rl[2*i+1]) // 2
    if rl[2*i] % 2 == rl[2*i+1] % 2:
        ans[idx] = ans[idx+1] = cnt
    elif rl[2*i] % 2 == 0:
        ans[idx] = cnt
        ans[idx+1] = cnt + 1
    else:
        ans[idx] = cnt + 1
        ans[idx+1] = cnt
    

print(*ans)

Measured memory_bytes: 11024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  string s; cin >> s;
  int ans = 0;
  rep(i,sz(s)) if(s[i]=='1') ans++;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 1e5 + 5;
 
int32_t main()
{
	IOS;
	double r;
	cin >> r;
	cout << fixed << setprecision(12) << 2 * acosl(-1.0l) * r;
	return 0;
}

Measured memory_bytes: 3800
#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

//const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 1'000'000'000'000'000'000ll + 7;
//const i64 inf = 1'000'000'007;

const long double eps = 1e-8;

const i64 MAXN = 100'000 + 5;

i64 z;

inline i64 mult(i64 a) {
    return a * a * a * a * a;
}

i64 calc(i64 a, i64 b) {
    return mult(a) - mult(b);
}

pair<i64, i64> brute() {
    i64 v = 1000;
    i64 vmin = -v;
    i64 vmax = v;

    for (i64 x = vmax; x >= vmin; x--) {
        for (i64 y = vmax; y >= vmin; y--) {
            i64 r = calc(x, y);
            if (r == z) {
                return { x, y };
            }
        }
    }

    throw 1;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    //for (i64 i = 1; i <= 1000; i++) {
    //    cerr << (i64)pow(i, 5) - (i64)pow(i - 1, 5) << endl;
    //}

    cin >> z;
    auto p = brute();

    cout << p.first << " " << p.second << endl;



    return 0;
}

Measured memory_bytes: 3612
#include <algorithm>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;

int main() {
  //
  ll n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;
  rep(i, n) {
    if (c * (n - 1 - i) - d * i <= b - a && b - a <= -c * i + (n - 1 - i) * d) {
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
  return 0;
}


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

using namespace std;

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

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

typedef pair<long long int, long long int> P;

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		long long int t = 1;
		vector<long long int> d(n);
		vector<long long int> v(n);
		for (int i = 0; i < n; i++) {
			cin >> d[i] >> v[i];
			t = lcm(max(v[i]*t, d[i]), min(v[i]*t, d[i])) / v[i];
			//cout << t << endl;
		}
		long long int a = v[0]*t/d[0];
		for (int i = 0; i < n; i++) {
			a = gcd(a, v[i]*t/d[i]);
		}
		for (int i = 0; i < n; i++) {
			cout <<(v[i]*t/d[i])/a << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,k,a[N],b[N],c[N],tot;
int main(){
	scanf("%d%d",&n,&k);k--;
	for (int i=1;i<=n/2;i++){
		a[++tot]=i;
		b[tot]=i+n+n/2;
		a[++tot]=i+(n+1)/2;
		b[tot]=i+n;
	}
	if (n&1)a[++tot]=(n+1)/2,b[tot]=n+n;
	for (int i=1;i<=n;i++)c[i]=2*n+k+i,a[i]+=k,b[i]+=k;
	for (int i=1;i<=n;i++)
		if ((long long)a[i]+b[i]>c[i]){
			puts("-1");
			return 0;
		}
	for (int i=1;i<=n;i++)printf("%d %d %d\n",a[i],b[i],c[i]);	
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    queue<int> A[N];
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N-1; ++j){
            int tmp; cin >> tmp;
            A[i].push(tmp-1);
        }
    }

    bool flag[N];
    for(int i = 0; i < N; ++i) flag[i] = true;

    int day = 0;
    while(1){
        
        bool tmp = false;
        for(int i = 0; i < N; ++i) {
            if(!A[i].empty()) { tmp = true; break; }
        }
        if(!tmp) { break; }
        
        int cnt = 0;
        for(int i = 0; i < N; ++i) {
            if(flag[i] && !A[i].empty()) {
                int arrow = A[i].front();
                if(i == A[arrow].front() && flag[arrow]) {
                    A[i].pop(); A[arrow].pop();
                    flag[i] = flag[arrow] = false;
                    ++cnt;
                }
            }
        }
        if(cnt == 0) { day = -1; break; }
        for(int i = 0; i < N; ++i) flag[i] = true;
        ++day;

    }

    cout << day << endl;

    return 0;
}

Measured memory_bytes: 6784
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main(){
  int i,j,cnt;
  string s;
  cin>>s;
  int w1=0,w2=0,b1=0,b2=0;
  for(i=0;i<s.size();i++){
    if(i%2==0){
      if(s[i]=='0')w1++;
      else b1++;
    }else{
      if(s[i]=='0')w2++;
      else b2++;
    }
  }
  cout<<min(w1+b2,w2+b1);
}

Measured memory_bytes: 512
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int n = sc.nextInt();
		final int m = sc.nextInt();
		
		
		long[] xs = new long[n];
		long[] ys = new long[n];
		
		TreeSet<Long> x_set = new TreeSet<Long>();
		TreeSet<Long> y_set = new TreeSet<Long>();
		
		for(int i = 0; i < n ; i++){
			xs[i] = sc.nextLong();
			ys[i] = sc.nextLong();
			x_set.add(xs[i]);
			y_set.add(ys[i]);
		}
		
		x_set.add(Long.MIN_VALUE); y_set.add(Long.MIN_VALUE);
		x_set.add(Long.MIN_VALUE + 1); y_set.add(Long.MIN_VALUE + 1);
		x_set.add(Long.MAX_VALUE - 1); y_set.add(Long.MAX_VALUE - 1);
		x_set.add(Long.MAX_VALUE); y_set.add(Long.MAX_VALUE);
		ArrayList<Long> x_list = new ArrayList<Long>(x_set);
		ArrayList<Long> y_list = new ArrayList<Long>(y_set);
		
		
		final int y_size = y_list.size();
		final int x_size = x_list.size();
		long[][] map = new long[y_size][x_size];
		
		for(int i = 0; i < n; i++){
			final int x_index = Collections.binarySearch(x_list, xs[i]);
			final int y_index = Collections.binarySearch(y_list, ys[i]);
			
			map[y_index][x_index]++;
		}
		
		/*
		System.out.println();
		for(int i = 0; i < y_size; i++){
			for(int j = 0; j < x_size; j++){
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		*/
		
		for(int i = 0; i < y_size; i++){
			for(int j = 0; j < x_size; j++){
				if(i != 0){
					map[i][j] += map[i - 1][j];
				}
				
				if(j != 0){
					map[i][j] += map[i][j - 1];
				}
				
				if(i != 0 && j != 0){
					map[i][j] -= map[i-1][j-1];
				}
			}
		}
		
		//     0   1    2
		//  -1  -2   -3
		for(int i = 0; i < m; i++){
			final long lx = sc.nextLong();
			final long ly = sc.nextLong();
			final long hx = sc.nextLong();
			final long hy = sc.nextLong();
			
			int lx_index = Collections.binarySearch(x_list, lx);
			if(lx_index < 0){
				lx_index = -(lx_index + 1);
			}
			lx_index--;
			
			int hx_index = Collections.binarySearch(x_list, hx);
			if(hx_index < 0){
				hx_index = -(hx_index + 2);
			}
			
			int ly_index = Collections.binarySearch(y_list, ly);
			if(ly_index < 0){
				ly_index = -(ly_index + 1);
			}
			ly_index--;
			
			int hy_index = Collections.binarySearch(y_list, hy);
			if(hy_index < 0){
				hy_index = -(hy_index + 2);
			}
			
			//System.out.println(x_list);
			//System.out.println(lx_index + "," + ly_index + " <=>" + hx_index + ", " + hy_index);
			
			final long hh = map[hy_index][hx_index];
			final long hl = map[hy_index][lx_index];
			final long lh = map[ly_index][hx_index];
			final long ll = map[ly_index][lx_index];
			
			
			final long result = hh - hl - lh + ll;
			
			System.out.println(result);
		}
		
		
	}
}

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

W = S.count('W')
E = N - W

numW = 0
ans = N
for i in range(N):
    numE = N - i - (W - numW)
    if S[i]=='E':
        numE -= 1
    #print(i, S[:i], S[i+1:], numW, numE)
    ans = min(ans, numW + numE)
    if S[i]=='W':
        numW += 1

print(ans)


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

int main() {
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0;i < n;i++){
    cin >> s[i];
  }
  
  for (int i = 0;i < n;i++){
    sort(s[i].begin(), s[i].end());
  }
  sort(s.begin(),s.end());
  
  /*for (int i = 0;i < n;i++){
    cout << s[i] << endl;
  }*/
  
  long long ans = 0;
  long long c = 0;
  
  for (int i = 0;i < n;i++){
    if (i != n){
      if (s[i] == s[i+1]){
        c++;
        continue;
      }
      else{
        ans += (c+1)*c/2;
        c = 0;
      }
    }
    else{
      ans += (c+1)*c/2;
      c = 0;
    }
  }
  
  cout << ans << endl;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> cnt;
    for(int i=1; i<n; i++) {
        cin >> a[i];
        if(cnt.count(a[i]-1)) cnt.at(a[i]-1)++;
        else cnt[a[i]-1]=1;
    }
    for(int i=0; i<n; i++) {
        if(cnt.count(i)) cout << cnt.at(i) << endl;
        else cout << 0 << endl;
    }
}

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

using namespace std;

#define nfs                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);

int main() {
    nfs;

    int n;
    cin >> n;
    int h[n];
    int a[n] = {};

    for (auto& x : h) cin >> x;
    a[1] = abs(h[1] - h[0]);
    for (int i = 2; i < n; ++i) {
        a[i] = min(a[i - 2] + abs(h[i] - h[i - 2]),
                   a[i - 1] + abs(h[i] - h[i - 1]));
    }
    cout << a[n - 1] << endl;
}

Measured memory_bytes: 4396
#include <stdio.h>

int main(){
    int n;
    int i;
    long min = 2147483647;
    long max = -2147483648;
    long sum = 0;
    int input;

    scanf("%d", &n);
    
    
    for (i = 0;i < n;i++){
        scanf("%d",  &input);
    
        if(input < min){
            min = input;
        }
    
        if(input > max){
            max = input;
        }
    
        sum += input;
    }
    
    printf("%ld %ld %ld\n", min, max, sum);
    
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  
  vector<int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a.at(i);
  }
  
  int i = 0, x = 0;
  
  for (i = 0; i < n; i++){
    if (a.at(x) == 2){
      cout << i+1 << endl;
      break;
    }
    
    x = a.at(x)-1;
  }
  
  if (i == n)
    cout << -1 << endl;
  
}

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

typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;


//===

const ll mod = ll(1e9 + 7);



int main() {
	int n;
	cin >> n;
	Vi p(n);
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
	}
	int ans = 0;
	for (int i = 1; i < n - 1; ++i) {
		int pl = p[i - 1], pr = p[i + 1];
		if (p[i] < max(pl, pr) && p[i] > min(pl, pr)) ++ans;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<utility>
#include<cmath>

using namespace std;


int main()
{
  int N;
  cin >> N;

  vector<int> H(N);

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

  for(int i = N-1; i >= 1; i--){
    if( H[i-1] > H[i] ){
      H[i-1] -= 1;
      if((H[i-1] > H[i])){
        cout << "No" << endl;
        return 0;
      }
    }
  }

  cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int t,m,n,c=0,mn=0x7fffffff;;
    cin>>n;
    long long int v[n+10];
    m=0;
    for(long long int i=1; i<=n; i++)
    {
        cin>>v[i];
        c+=v[i];
    }
    for(long long int i=1; i<n; i++)
    {
        m=m+v[i];
        long long int x=abs(2*m-c);
        mn=min(mn,x);

    }
    cout<<mn<<endl;
    return 0;
}


Measured memory_bytes: 1792
N,W=map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]



dp = [[0 for i in range(W+1)] for j in range(N+1)]


for i in range(N):
    for w in range(W+1):
        if w>=A[i][0]:
            dp[i+1][w] = max([dp[i][w-A[i][0]]+A[i][1], dp[i][w]])
        else:
            dp[i+1][w] = dp[i][w]
        
print(int(dp[N][W]))

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

int main(){
  int a,b;
  string s;
  cin >> a >> b;
  int count=0;
  for(int i=a;i<=b;i++){
    s=to_string(i);
    if(s[0]==s[4]&&s[1]==s[3]){
      count ++;
    }
  }
  cout << count << endl;
}

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

typedef long long ll;
typedef pair<int,int> ii;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int a,b; cin>>a>>b;
	cout<<max({a+b,a-b,a*b})<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define __ ios_base::sync_with_stdio(0);cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define forn(i,a,n) for(int i=a; i < n; i++)
typedef long long int lli;
typedef long double Double;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int mod = 1e9+7;
const int maxn = 100005;
const int inf = 1e9;
lli dp[2005];
int s;

lli solve(int sum){
	if(sum > s) return 0;

	if(sum == s) return 1;

	lli &res = dp[sum];
	if(res != -1) return res;
	res = 0ll;

	for(int i=3; true; i++){
		if(sum + i <= s){
			res = (res + solve(sum+i)) % mod;
		}
		else break;
	}

	return res;
}
int main(){__
	cin >> s;
	memset(dp,-1,sizeof(dp));
	cout << solve(0) << endl;
	return 0;
}


Measured memory_bytes: 3656
#include <algorithm>
#include <map>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <numeric>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define IREP(it,array) for(vector<int>::iterator it=array.begin(); it!=array.end(); ++it)
#define PREP(it,array) for(vector<P>::iterator it=array.begin(); it!=array.end(); ++it)
#define SREP(it,array) for(vector<string>::iterator it=array.begin(); it!=array.end(); ++it)

#define MP       make_pair
#define PB       push_back
#define ALL(x)   (x).begin(),(x).end()

const int INF = 1<<29;
const double EPS = 1e-9;
double zero(double d){
  return d < EPS ? 0.0 : d;
}

typedef long long LL;
typedef pair<int,int> P;



int main()
{
  cout.setf(ios::fixed, ios::floatfield);
  cout.precision(7);

  float xa,ya,xb,yb,xc,yc,xd,yd;
  while( scanf( "%f,%f,%f,%f,%f,%f,%f,%f", &xa,&ya,&xb,&yb,&xc,&yc,&xd,&yd ) != EOF ){
    if( signbit((xa-xc)*(yb-ya)+(ya-yc)*(xa-xb)) == 
        signbit((xa-xc)*(yd-ya)+(ya-yc)*(xa-xd)) ||
        signbit((xb-xd)*(ya-yb)+(yb-yd)*(xb-xa)) == 
        signbit((xb-xd)*(yc-yb)+(yb-yd)*(xb-xc)) )
      cout << "NO" << endl;
    else
      cout << "YES" << endl;
  }
  
  

  return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
const int ninf = 0xc0c0c0c0;
const double pi = acos(-1);
using db = double;
const int max_v = 200005;
int n,m;
int prevv[max_v];        
struct edge
{
    int to,cost;
    edge(int to,int cost){
    	this->to = to;
    	this->cost = cost;
	}
};
typedef pair<int,int> pii;       
int V;
vector<edge> G[max_v];
int d[max_v];
void dijkstra(int s)
{
    priority_queue<pii,vector<pii>,greater<pii> > q;          
    fill(d,d+V,inf);
    fill(prevv,prevv+V,-1);                                                                   
    d[s]=0;
    q.push(pii(0,s));
    while(!q.empty())
    {
        pii p=q.top();
        q.pop();
        int v=p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<G[v].size();i++)
        {
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost)
            {
                d[e.to]=d[v]+e.cost;
                prevv[e.to]=v;                                  
                q.push(pii(d[e.to],e.to));
            }
        }
     } 
}
 
vector<int> get_path(int t)
{
    vector<int> path;
    for(;t!=-1;t=prevv[t]) path.push_back(t);
    reverse(path.begin(),path.end());
    return path;
}
int main(){
	cin>>n>>m;
	V=n+1;
	for(int i=0;i<m;i++){
		int t1,t2;
		cin>>t1>>t2;
		G[t1].push_back(edge(t2,1));
		G[t2].push_back(edge(t1,1));
	}
	dijkstra(1);
	bool ok=true;
	for(int i=2;i<=n;i++){
		if(prevv[i]==-1) {
			ok=false;break;
		}
	}
	if(ok){
		puts("Yes");
		for(int i=2;i<=n;i++){
			cout<<prevv[i]<<endl;
		}
	}else{
		puts("No");
	}
	//cout<<d[1]<<" "<<d[2]<<" "<<d[3]<<d[4];
	return 0;
}

Measured memory_bytes: 15988
n = int(input())
s = input()

l = len(s)

dp = [[0] * (l + 1) for _ in range(l + 1)]

ans = 0
for i, ei in enumerate(s, 1):
    for j, ej in enumerate(s[i:], i+1):
        if ei == ej:
            dp[i][j] = min(dp[i-1][j-1] + 1, j - i)
            ans = max(ans, dp[i][j])

print(ans)


Measured memory_bytes: 230664
import sys
def main():
    s = input()
    if len(s) % 2 == 1:
        print('No')
        sys.exit()
    s1 = s[::2]
    s2 = s[1::2]
    s1t = [c == 'h' for c in s1]
    s2t = [c == 'i' for c in s2]
    if all(s1t) and all(s2t):
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()


Measured memory_bytes: 8976
#include<bits/stdc++.h>
using namespace std ;
#define loop(i,a,b)  for(int i=a;i<b;i++)
int main()
{   string s,t;cin>>s>>t;
      sort(s.begin(),s.end());
      sort(t.rbegin(),t.rend()) ;int i;
      for( i=0;s[i]&&t[i];i++) {
      if(int(s[i])<int(t[i])){cout<<"Yes"<<endl;exit(0);}
	  else if (int(s[i])>int(t[i])){cout<<"No"<<endl;exit(0);}}
	  if(int(s[i])) {cout<<"No"<<endl;exit(0);}
	  else if(int(t[i])){cout<<"Yes"<<endl;exit(0);}
	  else cout<<"No"<<endl;
      
}

Measured memory_bytes: 256
//
//  main.cpp
//  AGC031 -a
//
//  Created by hiroaki on 2019/03/16.
//  Copyright © 2019年 hiroaki. All rights reserved.
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;

int main() {
    long n;
    string s,S;
    cin >>n>>s;
    S=s;
    sort(s.begin(), s.end());
    decltype(s)::iterator result = std::unique(s.begin(), s.end());
    s.erase(result,s.end());
    long sum = 1;
    long l = s.size();
    for (int i=0; i<l; i++) {
        long e =count(S.begin(), S.end(), s[i]);
        sum *= (e+1);
        sum = sum % 1000000007;
    }
    cout<<sum-1<<endl;
    return 0;
}



Measured memory_bytes: 512
#include <stdio.h>

int main()
{
        int i = 0, x, n;

        scanf("%d", &n);

        while(++i <= n) {
                x = i;
                if (x % 3 == 0 || x % 10 == 3) {
                        printf(" %d", i);
                } else {
                        while (x) {
                                x /= 10;
                                if (x % 10 == 3) {
                                        printf(" %d", i);
                                        break;
                                }
                        }
                }
        }
        printf("\n");
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define fi first
#define se second
//#define int long long
using namespace std;
const int N = 5e6 + 1;
int mn[N], mx[N], pr[N], p[N], v;
 
void als(int i, int j) {
    i += v - 2;
    mn[i] = j;
    mx[i] = j;
    while (i > 0) {
        i = (i - 1) / 2;
        mn[i] = min(mn[2 * i + 1], mn[2*i + 2]);
        mx[i] = max(mx[2 * i + 1], mx[2*i + 2]);
    }
}
 
int mnn(int v, int vl, int vr, int l, int r) {
    if (l <= vl && vr <= r)
        return mn[v];
    else if (l >= vr || vl >= r)
            return 1e9;
        else
            return min(mnn(2*v + 1, vl, (vl + vr) / 2, l, r), mnn(2*v + 2, (vl + vr) / 2, vr, l, r));
}
 
int mxx(int v, int vl, int vr, int l, int r) {
    if (l <= vl && vr <= r)
        return mx[v];
    else if (l >= vr || vl >= r)
            return 0;
        else
            return max(mxx(2*v + 1, vl, (vl + vr) / 2, l, r), mxx(2*v + 2, (vl + vr) / 2, vr, l, r));
}
 
 
signed main() {
    int i, j, k, n, x, q, H, W, A, B;
    //freopen("input.txt", "r", stdin);
    cin >> n >> k;
if (k == n) {
cout << 1;
exit(0);
}    
v = 1;
    while (v < n)
        v *= 2;
    for (i = 1; i <= n; ++i) {
        cin >> p[i];
        als(i, p[i]);
    }
    for (i = 2; i <= n; ++i)
        pr[i] = pr[i - 1] + (p[i] > p[i - 1]);
    int ans = 0;
    for (i = k; i <= n; ++i)
    if (pr[i] - pr[i - k + 1] == k - 1)
        ans = 1;
    if (k != n && pr[k] != k - 1)
        ++ans;
    for (i = 2; i <= n - k + 1; ++i)
    if (pr[i + k - 1] - pr[i] != k - 1 && ((p[i - 1] != mnn(0, 1, v + 1, i - 1, i + k - 1) || (p[i + k - 1] != mxx(0, 1, v + 1, i, i + k))))) {
        ++ans;
    }
    cout << ans;
}

Measured memory_bytes: 9216
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Foldable
import           Data.Maybe

readInt = fst . fromJust . BS.readInt
getInt = readInt <$> BS.getLine

main = do
  n <- getInt
  s <- getLine

  let nW = length $ filter (== '.') s

      solve nB nW [] res = min res (nB + nW)
      solve nB nW (c:cs) res | c == '.' = solve nB (nW-1) cs (min res (nB + nW))
                             | c == '#' = solve (nB+1) nW cs (min res (nB + nW))

  print $ solve 0 nW s (10^9)

Measured memory_bytes: 13820
def solve():
  n = int(input())
  h = list(int(i) for i in input().split())
  ans = 0
  tmp = 0
  for i in range(n-1):
    if h[i+1] <= h[i]:
      tmp += 1
    else:
      ans = max(ans,tmp)
      tmp = 0
  ans = max(ans,tmp)
  print(ans)
    
solve()

Measured memory_bytes: 15020
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
#define ll long long
int main()
{
    ll n,k;
    cin>>n>>k;
    ll p[n],c[n];
    for(int i=0; i<n; i++) cin>>p[i];
    for(int i=0; i<n; i++) cin>>c[i];
    vector<ll>maxin[n];
    vector<ll>real[n];
    for(int i=0; i<n; i++) {
        ll ans=0,mx=-1e18,cur=p[i];
        while(1) {
            ans+=c[cur-1];
            mx=max(mx,ans);
            maxin[i].push_back(mx);
            real[i].push_back(ans);
            cur=p[cur-1];
            if(cur==p[i])break;
        }
    }
    ll ans=-1e18;
    for(int i=0; i<n; i++) {
        long long int t=k%maxin[i].size();
        ll s=real[i].size();
        ll e;
        if(t==0) e=0;
        else e=maxin[i][t-1];
        ll y=0;
        if(k/s>1)
            y=real[i][s-1]*(k/s-1)+maxin[i][s-1];
        if(k<=s) ans=max(ans,maxin[i][k-1]);
        else ans=max(ans,max(real[i][s-1]*(k/s)+e,
                                 max(y,maxin[i][s-1])));
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 434360
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL,LL>PL;
const LL INF=1e18;
const LL MOD=1e9+7;
LL N,i,ans;
char S[1234567];
LL C[258];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N;
    cin>>S;
    for(i=0;i<N;i++)
        C[S[i]-'a']++;
    N=1;
    for(i=0;i<26;i++)
    {
        ans=(ans+N*C[i])%MOD;
        N=N*(C[i]+1)%MOD;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>

int main(void) {
  int N, M;
  int rinsetu[60][60] = {0};
  int i, j;
  
  scanf("%d %d", &N, &M);
  for(i = 0; i < M; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--; b--;
    rinsetu[a][b] += 1;
    rinsetu[b][a] += 1;
  }
  for(i = 0; i < N; i++) {
    int tmp = 0;
    for(j = 0; j < N; j++) {
      tmp += rinsetu[i][j];
    }
    printf("%d\n", tmp);
  }
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

template <typename T>
T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template <typename T>
T lcm(T a, T b) { return (a * b) / gcd(a, b); }

bool check(vector<Int> a) {
	Int b = 1;
	while (a[0] % (2 * b) == 0) { b *= 2; }
	for (auto v : a) {
		if (v % b != 0 || (v / b) % 2 == 0) { return false; }
	}
	return true;
}

int main() {
	Int N, M;
	cin >> N >> M;
	vector<Int> a(N);
	for (int i = 0; i < N; ++i) { cin >> a[i]; }

	if (!check(a)) {
		cout << 0 << endl;
		return 0;
	}

	Int l = a[0] / 2;
	for (int i = 0; i < N; ++i) {
		l = lcm(l, a[i] / 2);
		if (l > M) { break; }
	}

	Int ans = (M / l + 1) / 2;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1792
from sys import stdin,stdout
from itertools import accumulate
n=int(stdin.readline());M=10**9+7
a=list(map(int,stdin.readline().split()))
ps=list(accumulate(a[::-1]))[::-1]
ans=0
for i in range(n-1):
    ans=(ans+a[i]*(ps[i+1]))%M
print(ans%M)

Measured memory_bytes: 31432
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;


int main(){
  int n,k,q;
  cin >> n >> k >> q;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];
  ll ans = longinf;
  rep(i,n){
    vector<vector<ll>> ch;
    ch.push_back({});
    rep(j,n){
      if(a[j]>=a[i]){
        ch.back().emplace_back(a[j]);
      } else {
        ch.push_back({});
      }
    }
    vector<ll> b;
    for(auto& it:ch){
      sort(it.rbegin(),it.rend());
      while(it.size()>=k){
        b.emplace_back(it.back());
        it.pop_back();
      }
    }
    sort(b.begin(),b.end());
    if(b.size()>=q) ans = min(ans, b[q-1]-b[0]);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
#include <string>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <iostream>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <cmath>
#include <limits>
#include <tuple>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()

int main()
{
	string S;
	cin >> S;
	ll K;
	cin >> K;
	int N = (int)min(K, (ll)S.size());
	int ans = 1;
	for (int i = 0; i < N; i++) {
		if (S[i] != '1') {
			ans = S[i] - '0';
			break;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int N;
    cin >> N;

    string S;
    cin >> S;

    int ans = 0;

    for (int i = 1; i < N; i++){
        int cnt = 0;
        for (char c = 'a'; c <= 'z'; c++){
            bool left = false, right = false;

            for (int j = 0; j < i; j++){
                if(S[j] == c){
                    left = true;
                }
            }

            for (int j = i; j < N; j++){
                if (S[j] == c){
                    right = true;
                }
            }

            if (left && right){
                cnt++;
            }
        }
        if (ans < cnt){
            ans = cnt;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256