akhauriyash/Code-Regression huggingface dataset:
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
char s[10];
int main()
{
	scanf("%s",s);
	if(s[0]=='S')
		puts("Cloudy");
	else if(s[0]=='R')
		puts("Sunny");
	else
		puts("Rainy");
	return 0;
}


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

int main() {
    ll n,m,ans=0;
    cin>>n>>m;
    vector<ll> h(n);
    for(ll i=0; i<n; i++) cin>>h[i];
    vector<ll> a(m),b(m);
    for(ll i=0; i<m; i++) cin>>a[i]>>b[i];
    vector<ll> d(n);
    for(ll i=0; i<m; i++) {
        if(h[a[i] - 1] < h[b[i] - 1]) d[a[i] - 1]++;
        else if(h[a[i] - 1] > h[b[i] - 1]) d[b[i] - 1]++;
      	else {
              d[a[i] - 1]++; d[b[i] - 1]++;
          }
    }
    for(int i=0; i<n; i++) {
        if(d[i] == 0) ans++;
    }
    cout<<ans;
}

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

string s;

int main(){
    cin>>s;
    if(s[0]==s[1]){
        if(s[2]==s[3] && s[2]!=s[0]){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    if(s[0]==s[2]){
        if(s[1]==s[3] && s[1]!=s[0]){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    if(s[0]==s[3]){
        if(s[2]==s[1] && s[2]!=s[0]){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

ll bread[51], patty[51];

int c = 0, d = 0;

ll rec(ll n, ll x) {
  if (n == 0)
    return 1;
  if (x == 1)
    return 0;

  ll mid = (bread[n] + patty[n]) / 2 + 1;
  ll ans = 0;
  if (x > mid) {
    ans += patty[n - 1] + 1;
    x -= bread[n - 1] + patty[n - 1] + 1;
    c++;
  } else if (x == mid)
    return patty[n - 1] + 1;
  d++;
  ans += rec(n - 1, x - 1);
  return ans;
}

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

  ll n, x;
  cin >> n >> x;
  bread[0] = 0, patty[0] = 1;
  rep(i, 1, 51) {
    bread[i] = bread[i - 1] * 2 + 2;
    patty[i] = patty[i - 1] * 2 + 1;
  }

  if (n >= x) {
    cout << 0 << endl;
    return 0;
  }
  ll ans = rec(n, x);
  cout << ans << endl;
}


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

int main(){
  
  int n;
  cin >>n;
  int a[n];
  vector<int> b(n);
  for(int i=0; i<n; i++){
    cin >> a[i];
    b[i]=a[i];
  }
  sort(b.begin(),b.end());
  reverse(b.begin(),b.end());
  
  for(int i=0; i<n; i++){
    if(a[i]==b[0]) cout<< b[1] << endl;
    else cout << b[0] << endl;
  }
  
}

Measured memory_bytes: 3200
#include<stdio.h>
int min(int a, int b){return a < b ? a : b;}
int main(){
    int a[5], i = 0;
    int ans = 0;
    for(; i < 5; i++)
        scanf("%d",&a[i]);
    int MIN = 10;
    for(i = 0; i < 5; i++){
        if(MIN > a[i] % 10 && a[i] % 10 != 0)
            MIN = a[i] % 10;
        ans += (a[i] - 1) / 10 * 10 + 10;
    }
    printf("%d\n",ans -10 + MIN);
    return 0;
}

Measured memory_bytes: 128
/**
 * Created by Wangzhe on 2020/1/12 19:56.
 * Description: 
 **/


#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define PI acos(-1.0)
#define eps 1e-12
#define fi first
#define se second
#define MEM(a, b) memset((a),(b),sizeof(a))
#define mod(x) ((x)%MOD)
#define pii pair<int,int>
#define wz cout<<"-----"<<endl;

const int INF_INT = 2147483647;
const ll INF_LL = 9223372036854775807LL;
const ull INF_ULL = 18446744073709551615Ull;
const ll P = 92540646808111039LL;

const ll maxn = 1e5 + 10, MOD = 1e9 + 7;

ll fac[maxn];
ll rfac[maxn];

ll qpow(ll a, ll b) {
    ll r = 1;
    while (b) {
        if (b & 1) {
            r = (r * a) % MOD;
        }
        b >>= 1;
        a = (a * a) % MOD;
    }
    return r;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i <= 1e5; i++) {
        fac[i] = (fac[i - 1] * i) % MOD;
    }
    rfac[int(1e5)] = qpow(fac[int(1e5)], MOD - 2);
    for (int i = 1e5; i > 0; i--) {
        rfac[i - 1] = (rfac[i] * i) % MOD;
    }
}
ll a[maxn];

ll C(int n, int k) {
    if (n < k) return 0;
    return (((fac[n] * 1ll * rfac[k]) % MOD) * rfac[n - k]) % MOD;
}

ll n, k;
void solve() {
    cin >> n >> k;
    ll sum = 0;
    for (int i = 0;i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        int t = C(i, k - 1);
        sum = (sum + a[i] * t) % MOD;
    }
    for (int i = 0; i < n; i++) {
        int t = C(i, k - 1);
        sum = (sum - a[n - i - 1] * t + MOD) % MOD;
    }
    cout << sum << endl;
}


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

Measured memory_bytes: 2560
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;

		while(!(str=br.readLine()).equals("0")){
			int n = Integer.parseInt(str);
			System.out.println(fact(n));
		}
	}

	static int fact(int n){
		int c=0;

		while(n>=5){
			c += n/5;
			n/=5;
		}
		return c;
	}

}

Measured memory_bytes: 16856
program grouping
  implicit none
  integer :: x, y, z(12)
  z = (/1,3,1,2,1,2,1,1,2,1,2,1/)
  read(*,*) x, y
  if (z(x).eq.z(y)) then
    write(*,'(a)') "Yes"
  else
    write(*,'(a)') "No"
  end if
end program grouping

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

using namespace std;

char s[100005];

int n, ans;

void solve() {
    scanf("%s", s);

    for (n = 0; s[n]; ++n);

    for (int l = 0; l < n; ++ans) {
        int r = l;

        while (s[r] == s[l]) {
            ++r;
        }

        l = r;
    }

    printf("%d\n", ans - 1);
}

int main() {
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>
#include<random>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
int d;
int c[30]={};
int s[370][30];
int num=260000;
int koho=5;
int calc(vector<int>const& t,vector<vector<int>>& last_list){
  int res=0;
  vector<int> last(30,0);
  rep1(i,d){
    res+=s[i][t[i]];
    last[t[i]]=i;
    last_list[i]=last;
    int buf=0;
    rep1(j,26){
      buf+=c[j]*(i-last[j]);
    }
    res-=buf;
    //cout<<res<<"\n";
  }
  return res;
}
int change(int nd,int nq,int& res,vector<int>& t,vector<vector<int>>& last_list){
  int flag_t=false;
  int flag_q=false;
  int x=t[nd];
  t[nd]=0;
  res+=s[nd][nq];res-=s[nd][x];
  for(int i=nd;i<=d;++i){
    if(flag_t&&flag_q)break;
    if(t[i]==x||flag_t)flag_t=true;
    else{
      res+=c[x]*(i-last_list[i][x]);
      last_list[i][x]=last_list[i-1][x];
      res-=c[x]*(i-last_list[i][x]);
    }
    if(t[i]==nq||flag_q)flag_q=true;
    else{
      res+=c[nq]*(i-last_list[i][nq]);
      last_list[i][nq]=nd;
      res-=c[nq]*(i-last_list[i][nq]);
    }
  }
  t[nd]=nq;
  return res;
}
vector<int> greedy(int d,vector<vector<int>>& t_koho){
  vector<int> res(d+1,0);
  vector<int> last(30,0);
  rep1(i,d){
    int mx=-inf;
    int mx_ind=0;
    vector<P> kouho(26);
    rep1(j,26){
      int tmp=s[i][j];
      rep1(k,26){
        if(k==j)continue;
        tmp-=c[k]*(i-last[k]);
      }
      if(mx<tmp){
        mx=tmp;
        mx_ind=j;
      }
      kouho[j-1]={tmp,j};
    }
    sort(kouho.begin(),kouho.end());
    reverse(ALL(kouho));
    rep(x,koho){
      t_koho[i][x]=kouho[x].second;
    }
    last[mx_ind]=i;
    res[i]=mx_ind;
  }
  return res;
}
signed main(){
  cin>>d;
  rep1(i,26)cin>>c[i];
  rep1(i,d){
    rep1(j,26)cin>>s[i][j];
  }
  vector<vector<int>> t_koho(d+5,vector<int>(koho+5,0));
  vector<int> t=greedy(d,t_koho);
  vector<vector<int>> last_list(d+1,vector<int>(30,0));
  int res=calc(t,last_list);
  //cout<<res<<"\n";
  int param=1;
  rep(xx,num){
    random_device rand;
    mt19937 mt(rand());
    int dev=koho;
    if(xx>num/2)dev/=2;
    vector<int> nd(param);
    rep(i,param){
      nd[i]=mt()%(d-1)+1;
    }
    vector<int> bq(param);rep(i,param)bq[i]=t[nd[i]];
    int bval=res;
    rep(i,param){
      change(nd[i],t[nd[i]+1],res,t,last_list);
      change(nd[i]+1,bq[i],res,t,last_list);
    }
    int yakinamasi=mt()%100;
    //if(yakinamasi<(20-(xx*30)/num)&&res+res/10000>bval)continue;
    if(bval>res){
      rep(i,param){
        change(nd[i]+1,t[nd[i]],res,t,last_list);
        change(nd[i],bq[i],res,t,last_list);
      }
    }
  }
  rep1(i,d){
    cout<<t[i]<<"\n";
  }
  //cout<<res<<"\n";
  return 0;
}

Measured memory_bytes: 3840
fn solve() {
    let n = read();
    let mut vs: Vec<usize> = vec![];
    for _ in 0..n {
        vs.push(read());
    }
    let mut buyt = HashSet::new();
    let mut sellt = HashSet::new();
    for i in 0..n - 1 {
        if vs[i] < vs[i + 1] {
            buyt.insert(i);
        } else if vs[i] > vs[i + 1] {
            sellt.insert(i);
        }
    }
    sellt.insert(n - 1);
    let mut cur = 1000;
    let mut stocks = 0;
    for i in 0..n {
        if buyt.contains(&i) {
            stocks += cur / vs[i];
            cur %= vs[i];
        } else if sellt.contains(&i) {
            cur += stocks * vs[i];
            stocks = 0;
        }
    }
    println!("{}", cur);
}

fn main() {
    let stack_size = 104_857_600;
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

// =========
#[allow(unused_imports)]
use std::cmp::{max, min, Reverse};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: usize = 1000000007;

fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// =========


Measured memory_bytes: 2236
# 訂正
class UnionFind:
    __slots__ = ["N", "root", "rank"]

    def __init__(self, N):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        rank:ランク
        """
        self.N = N
        self.root = [-1] * N

    def __repr__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    def find(self, x):
        """頂点xの根を見つける"""
        while self.root[x] >= 0:
            x = self.root[x]
        return x

    def union(self, x, y):
        """x, yが属する木をunion"""
        # 根を比較する
        # すでに同じ木に属していた場合は何もしない.
        # 違う木に属していた場合はrankを見てくっつける方を決める.
        # rankが同じ時はrankを1増やす
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.root[y] < self.root[x]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

    def same(self, x, y):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find() == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        """連結成分の数"""
        return len(self.roots())

    def all_group_members(self):
        """{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}


import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = UnionFind(n)
res = []
for i in range(q):
    t, u, v = map(int, input().split())
    if t:
        res.append(int(uf.same(u, v)))
    else:
        uf.union(u, v)
print("\n".join(map(str, res)))


Measured memory_bytes: 85540
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int[][] A = new int[3][3];
		int N;
		int b;
		int i;
		int j;
		int n;
		int flag = 0;
		Scanner sc = new Scanner(System.in);
		for (i = 0; i < 3; i++) {
			for (j = 0; j < 3; j++) {
				A[i][j] = Integer.parseInt(sc.next());
			}
		}
		N = Integer.parseInt(sc.next());
		for (n = 0; n < N; n++) {
			b = Integer.parseInt(sc.next());
			for (i = 0; i < 3; i++) {
				for (j = 0; j < 3; j++) {
					if (A[i][j] == b) {
						A[i][j] = 0;
						flag = 1;

						break;
					}
				}
				if (flag == 1) {
					flag = 0;
					break;
				}
			}
		}
		sc.close();
		for (i = 0; i < 3; i++) {
			if ((A[i][0] == A[i][1] && A[i][1] == A[i][2])||(A[0][i] == A[1][i] && A[1][i] == A[2][i])) {
				System.out.println("Yes");
				return;
			}
		}
		if (A[0][0] == A[1][1] && A[1][1] == A[2][2] || A[0][2] == A[1][1] && A[1][1] == A[2][0]) {
			System.out.println("Yes");
			return;
		}
		System.out.println("No");
	}
}

Measured memory_bytes: 22228
use List::Util qw/first reduce max/;
my $n = <stdin>;
chomp($n);
my @a;
push @a, $_ for (<stdin>);
my $c = 0;
my $i = 1;
while ($i != 2 && $c < $n){
   $i = $a[$i-1];
   $c++;
}
print ( $c < $n ? $c : -1);

Measured memory_bytes: 20224
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
const vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} __init;
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>void debag(const vector<T> &a){cerr<<"debag :";for(auto v:a)cerr<<v<<" ";cerr<<"\n";}
template<class T>void print(const vector<T> &a){for(auto v:a)cout<<v<<" ";cout<<"\n";}
template<typename T>
struct BIT{
    //1-index
    //0-indexで取ると無限ループする
    private:
    V<T> arr;
    int n;

    public:
    BIT(int siz){
        n=siz;
        arr.assign(n+1,0);
    }
    //一点更新 aにvを加える
    void add(T a,T v){
        //x+=(x&-x) 初項a,それ以降a<=2^Nが列挙
        for(T x=a;x<=n;x+=(x&-x)){
            arr[x]+=v;
        }
    }
    T sum(T a){
        // 1からaまでの区間和
        T ret=0;
        for(T x=a;x>0;x-=(x&-x))ret+=arr[x];
        return ret;
    }
    T get(T x){//x番目に大きい数　// 区間和がw以上となる最小のindを返す
        if(x<=0) return 0;
        T N=1;
        while(N*2<=n)N*=2;
        T v=0;
        for(T i=N;i>0;i/=2){
            if(v+i<=n&&arr[v+i]<x){
                x-=arr[v+i];
                v+=i;
            }
        }
        return v+1;
    }
    T query(int l,int r){
        return sum(r)-sum(l);
    }
};
int main(){
    int n,q;
    cin>>n>>q;
    BIT<ll> bit(n+5);
    ll a;
    for(int i=0;i<n;i++){
        cin>>a;
        bit.add(i+1,a);
    }
    ll t,l,r;
    while(q--){
        cin>>t>>l>>r;
        if(t){
            cout<<bit.query(l,r)<<"\n";
        }else{
            bit.add(l+1,r);
        }
    }   
}

Measured memory_bytes: 8260
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  if (S.at(K - 1) == 'A') {
    S.at(K - 1) = 'a';
  }
  else if (S.at(K - 1) == 'B') {
    S.at(K - 1) = 'b';
  }
  else {
    S.at(K - 1) = 'c';
  }
  cout << S << endl;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll N, W;
    cin >> N >> W;
    vector<P> items(N);
    rep(i, N) cin >> items[i].first >> items[i].second;

    ll min_num = INF;
    rep(i, N) {
        min_num = min(min_num, items[i].first);
    }

    vector<multiset<ll>> cnt(4);
    rep(i, N) {
        P p = items[i];
        cnt[p.first - min_num].insert(-p.second);
    }

    vector<vector<ll>> acc(4, vector<ll>(N + 1, 0));
    rep(i, 4) {
        auto itr = cnt[i].begin();
        ll last = 0;
        rep(j, cnt[i].size()) {
            acc[i][j + 1] += acc[i][j] + -*itr;
            itr++;
            last = j;
        }
    }
    ll ans = 0;
    rep(i, acc[0].size()) {
        rep(j, acc[1].size()) {
            rep(k, acc[2].size()) {
                rep(m, acc[3].size()) {
                    ll tmp = acc[0][i] - acc[0][0];
                    tmp += acc[1][j] - acc[1][0];
                    tmp += acc[2][k] - acc[2][0];
                    tmp += acc[3][m] - acc[3][0];
                    if ((i + j + k + m) * min_num + j + 2 * k + 3 * m <= W) {
                        ans = max(ans, tmp);
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
import sys

N = int(input())

xyh = []
minh = 0

for i in range(N):

    x,y,h = map(int,input().split())
    xyh.append([x,y,h])
    minh = max(minh,h)


for cx in range(101):

    for cy in range(101):

        for ch in range(201):

            flag = True
            ch += minh 

            for i in range(N):

                if xyh[i][2] == 0 and ch - abs(xyh[i][0] - cx) - abs(xyh[i][1] -cy) > 0:
                    flag = False
                    break

                elif xyh[i][2] != 0 and ch - abs(xyh[i][0] - cx) - abs(xyh[i][1] -cy) != xyh[i][2]:
                    flag = False
                    break

            if flag:
              print (cx,cy,ch)
              sys.exit()


Measured memory_bytes: 45292
/*
      @author: Charan Sai
*/
#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define ppi pair<int, int>
#define endl "\n"
#define nl cout << "\n"
#define deb(x) cout << #x << " " << x << endl;
#define itr(i, n) for(int i = 0; i < n; ++i)
#define itr1(i, a, n) for(int i = a; i < n; ++i)

const int INF = 1e18L + 5;
const int MAX_N = 1000;

int dp[MAX_N][MAX_N];
// int sum[MAX_N][MAX_N];

// int top_down(int i, int j) {
//     if(i == j) return 0;
//     // if(i > j) return INT_MAX;

//     if(dp[i][j] != -1) return dp[i][j];
//     int res = INF;
//     for(int k = i; k <= j-1; ++k) {
//         res = min(res, top_down(i, k) + top_down(k+1, j) + sum[i][j]);
//     }
//     return (dp[i][j] = res);
// }

int bottom_up(vector<int> &a) {
    memset(dp, -1, sizeof(dp));
    auto sum = [&](int i, int j) {
        int sum = 0;
        for(int k = i; k <= j; ++k) sum += a[k];
        return sum;
    };
    int n = (int)a.size();
    for(int i = n - 1; i >= 0; --i) {
        for(int j = 0; j < n; ++j) {
            if(i == j) dp[i][j] = 0;
            else {
                int s = sum(i, j);
                dp[i][j] = INF;
                for(int k = i; k < j; ++k) {
                    dp[i][j] = min(dp[i][j],
                                dp[i][k] + dp[k+1][j] + s
                            );
                }
            }
        }
    }

    return dp[0][n-1];
}

int32_t main() {
    // memset(sum, 0, sizeof(sum));
    IOS;
    int n; cin >> n;
    vector<int> a(n);
    for(int &x : a) cin >> x;
    // for(int i = 0; i < n; ++i) {
    //     for(int j = i; j < n; ++j) {
    //         if(j == 0) sum[i][j] = a[0];
    //         sum[i][j] = a[j] + sum[i][j-1];
    //     }
    // }
    cout << bottom_up(a) << endl;
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
const ll MOD = (ll)1e9+7;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}

class rolling_hash{
public:
	vector<int> prefix;

	vector<int> solve(const string &x, const string &y){
		const ll b = 17777;
		const ll h = 1e9+7;
		ll x_len = x.size();
		ll y_len = y.size();
		ll pow_b_y = 1;
		if(x_len<y_len)return vector<int>(0);

		ll x_hash = 0;
		ll y_hash = 0;
		rep(i, y_len){
			y_hash = y_hash * b + y[i];
			x_hash = x_hash * b + x[i];
			pow_b_y = pow_b_y * b;
			y_hash %= h;
			x_hash %= h;
			pow_b_y %= h;
		}
		prefix.clear();
		for(int i=y_len;i<=x_len;++i){
			if(x_hash==y_hash){
				prefix.emplace_back(i-y_len);
			}
			if(i<x_len){
				x_hash = x_hash * b - x[i-y_len] * pow_b_y + x[i];
				x_hash = (x_hash % h + h) % h;
				x_hash %= h;
			}
		}
		return prefix;
	}

};


int main(){
	string s, t;
	cin >> s >> t;
	rolling_hash r;
	vector<int> ans = r.solve(s, t);
	foreach(i, ans){
		cout << i << endl;
	}

	return 0;
}



Measured memory_bytes: 12168
#include<iostream>
#include<algorithm>
int f[200], s[200], t[200], sco[200];
int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++){
		std::cin >> f[i] >> s[i] >> t[i];
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (f[i] == f[j]){
				if (i!=j)
				break;
			}
			if (j == n - 1)
				sco[i] += f[i];
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (s[i] == s[j]){
				if (i != j)
				break;
			}
			if (j == n - 1)
				sco[i] += s[i];
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (t[i] == t[j]){
				if (i != j)
				break;
			}
			if (j == n - 1)
				sco[i] += t[i];
		}
	}
	for (int i = 0; i < n; i++){
		std::cout << sco[i] << "\n";
	}
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
#define mo 924844033
#define pi 3.1415926535898 
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long ksm(long long u,long long v){
	long long o=1;
	while(v){
		if(v&1)
			o=o*u%mo;
		u=u*u%mo;
		v>>=1;
	}
	return o;
}
long long n,k,i,j,jc[2005],a[2005],top,f[2005][2005][2][2],sum,ans;
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
   	n=read();k=read();
   	jc[0]=1;
   	for(i=1;i<=n;i++)
   		jc[i]=jc[i-1]*i%mo;
   	for(i=1;i<=k;i++)
   		for(j=i;j<=n;j+=k){
   			top++;
   			a[top]=j;
   		}
   	f[0][0][0][0]=1;
   	a[0]=-n;
   	for(i=1;i<=n;i++){
		f[i][0][0][0]=1;
		for(j=1;j<=i;j++){
			if(a[i]-a[i-1]!=k){
				f[i][j][0][0]=(f[i-1][j][1][0]+f[i-1][j][0][0])%mo;
				f[i][j][1][0]=(f[i-1][j][1][1]+f[i-1][j][0][1])%mo;
			}
			else{
				f[i][j][0][0]=(f[i-1][j][1][0]+f[i-1][j][0][0]+f[i-1][j-1][0][0])%mo;
				f[i][j][1][0]=(f[i-1][j][1][1]+f[i-1][j][0][1]+f[i-1][j-1][0][1])%mo;
			}
			if(a[i+1]-a[i]==k){
				f[i][j][0][1]=(f[i-1][j-1][1][0]+f[i-1][j-1][0][0])%mo;
				f[i][j][1][1]=(f[i-1][j-1][1][1]+f[i-1][j-1][0][1])%mo;
			}
		}
	}
   	for(i=0;i<=n;i++){
 		sum=(f[n][i][0][0]+f[n][i][0][1]+f[n][i][1][0]+f[n][i][1][1])*jc[n-i]%mo;
 		if(i&1)
 			ans=(ans-sum+mo)%mo;
 		else
 			ans=(ans+sum)%mo;
 	}
 	pus(ans,2);
    return 0;
}

Measured memory_bytes: 123776
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <array>
#include <random>
#include <complex>
#include <regex>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define quickIO()	{cin.tie(0);	cout.sync_with_stdio(false);}
#define reach(i,a)	for(auto i:a)
#define rep(i,n)	for(int i=0;i<((int)n);i++)
#define REP(i,n)	for(int i=0;i<=((int)n);i++)
#define srep(i,a,n)	for(int i=a;i<((int)n);i++)
#define SREP(i,a,n)	for(int i=a;i<=((int)n);i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
	for (T& x : vec)	is >> x;
	return is;
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
	os << "[";
	rep(i, vec.size())	os << (i ? ", " : "") << vec[i];
	os << "]";
	return os;
}
template<typename T>
istream& operator >> (istream& is, pair<T, T>& p) {
	is >> p.first >> p.second;
	return is;
}
template<typename T>
ostream& operator << (ostream& os, pair<T, T>& p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}
int bitcnt(ll x) {
	x = ((x & 0xAAAAAAAAAAAAAAAA) >> 1) + (x & 0x5555555555555555);
	x = ((x & 0xCCCCCCCCCCCCCCCC) >> 2) + (x & 0x3333333333333333);
	x = ((x & 0xF0F0F0F0F0F0F0F0) >> 4) + (x & 0x0F0F0F0F0F0F0F0F);
	x = ((x & 0xFF00FF00FF00FF00) >> 8) + (x & 0x00FF00FF00FF00FF);
	x = ((x & 0xFFFF0000FFFF0000) >> 16) + (x & 0x0000FFFF0000FFFF);
	x = ((x & 0xFFFFFFFF00000000) >> 32) + (x & 0x00000000FFFFFFFF);
	return x;
}
int bitcnt(int x) {
	x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
	x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
	x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
	x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
	x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
	return x;
}
ll sqrtll(ll x) {
	ll left = 0, right = x;
	rep(i, 100) {
		ll mid = (left + right) >> 1;
		if (mid*mid <= x)	left = mid;
		else	right = mid;
	}
	return left;
}
ll gcd(ll a, ll b) {
	return a % b == 0 ? b : gcd(b, a%b);
}
#define debug(x)	printf("Case #%d: ", x)
#define DEBUG 0
const ll inf = 1e9;
const ld infl = 1e100;
const ll mod = 998244353;
const ld eps = 1e-9;
const int dx[] = { 1,0,-1,0,0 };
const int dy[] = { 0,1,0,-1,0 };

int main() {
	int n, x;	cin >> n >> x;
	vint a(n);	cin >> a;
	sort(all(a));
	int ret = 0;
	while (ret < n && x >= a[ret]) {
		x -= a[ret++];
	}
	if (ret == n && x > 0)	ret--;
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <fstream>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef vector<pair<int, int> > vpii;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)
#define dbg(x) cout << #x"="<< (x) << endl
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back(a) 
#define in(x) cin >> x;
#define all(x) (x).begin(), (x).end()
#define INF 2147483600
#define fi first
#define se second
using namespace std;
int sum[3000];
int main(){
	int N;
	int ans = 0;
	while(cin>>N&&N){
		int index=0;
		ans = INT_MIN;
		FOR(i,1,N+1){
			cin>>sum[i];
			sum[i] += sum[i-1];
		}
		FOR(i,1,N+1){
			FOR(j,i,N+1){
				ans = max(ans,sum[j]-sum[i-1]);
			}
		}
		cout<< ans <<endl;
	}
}

Measured memory_bytes: 3028
N = int(input())
A = [int(x) for x in input().split(' ')]
B = [int(x) for x in input().split(' ')]
C = [int(x) for x in input().split(' ')]

ans = sum (B)
for i in range(N):
    if i < N - 1 and A[i+1] - A[i] == 1:
        ans += C[A[i] - 1]
print(ans)


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

using Lint=long long;

template<int mod> class ModInt
{
 private:
    Lint val;
 public:
    Lint value(){ return val; }
    ModInt(Lint x=0){ val=x%mod; }
    ModInt pow(int n){
        ModInt res(1),x(val);
        while(n>0){ if(n&1) res*=x; x*=x; n>>=1; }
        return res;
    }
    ModInt inv(){ return pow(mod-2); }
    ModInt& operator+=(ModInt rhs){ val+=rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator-=(ModInt rhs){ val+=mod-rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator*=(ModInt rhs){ val=val*rhs.val%mod; return *this; }
    ModInt& operator/=(ModInt rhs){ *this*=rhs.inv(); return *this; }
    ModInt operator+(ModInt rhs){ return ModInt(val)+=rhs; }
    ModInt operator-(ModInt rhs){ return ModInt(val)-=rhs; }
    ModInt operator*(ModInt rhs){ return ModInt(val)*=rhs; }
    ModInt operator/(ModInt rhs){ return ModInt(val)/=rhs; }
};
using mint=ModInt<1000000007>;

template<typename T> class BiCoef
{
 public:
    vector<T> fact,ifact,inv;
    BiCoef(int N):fact(N+1),ifact(N+1),inv(N+1){
        fact[0]=ifact[N]=inv[0]=1;
        for(int i=1;i<=N;i++) fact[i]=fact[i-1]*i;
        ifact[N]/=fact[N];
        for(int i=N-1;i>=0;i--) ifact[i]=ifact[i+1]*(i+1);
        for(int i=1;i<=N;i++) inv[i]=ifact[i]*fact[i-1];
    }
    T comb(int n,int k){
        if(n<0 or k<0 or n<k) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main()
{
   int N; cin>>N;
   vector<int> x(N);
   for(int i=0;i<N;i++) scanf("%d",&x[i]);

   BiCoef<mint> bc(N+1);
   mint ans=0;
   for(int i=0;i<N-1;i++){
      mint k=bc.fact[N-1]/(mint)(N-1-i);
      ans+=k*(x[N-1]-x[i]);
   }
   for(int i=0;i<N-1;i++){
      mint X=i;
      mint Y=(N-1)-(i+1);
      mint k=bc.fact[N-1]*(mint(1)/(Y+1)-mint(1)/(X+1));
      ans+=k*x[i];
   }
   cout<<ans.value()<<endl;
   return 0;
}


Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
const int N = 200100;

long long ret; 
long long n,a[N];
int main(){
    scanf("%lld",&n);
    for(int i=1; i<=n; i++){
    	scanf("%lld",&a[i]);
	}
    long long j=0,sum=0,xorsum=0;
	for(int i=1; i<=n; i++){
    	while(j+1<=n&&sum+a[j+1]==(xorsum^a[j+1])){
    		sum=sum+a[j+1];
		    xorsum=xorsum^a[j+1]; 
			j++;
		}
		ret+=j-i+1;
		sum-=a[i];
		xorsum^=a[i];
	}
	printf("%lld",ret); 
	return 0;
} 

Measured memory_bytes: 1792
import java.io.*;
import java.util.*;
import static java.lang.System.out;

public class Main {
    static MyReader in = new MyReader();

    public static void main(String[] args) {
        int N = in.i();
        int P = in.i();
        char[] S = in.s(N);
        long ans = solve(N, P, S);
        out.println(ans);
    }

    static long solve(int N, int P, char[] S) {
        long ans = 0;
        if (P == 2 || P == 5) {
            for (int i = 0; i < N; i++) {
                int j = S[i] - '0';
                if (j % P == 0) {
                    ans += i + 1;
                }
            }
        } else {
            int d = 1;
            int m = 0;
            int[] mod = new int[P];
            mod[0] = 1;
            for (int i = N - 1; i >= 0; i--) {
                m = ((S[i] - '0') * d + m) % P;
                mod[m]++;
                d = d * 10 % P;
            }
            for (int i = 0; i < P; i++) {
                ans += (long)mod[i] * (mod[i] - 1) / 2;
            }
        }
        return ans;
    }
}

class MyReader extends BufferedReader {
    char[] cbuf = new char[1024];
    int head = 0;
    int tail = 0;

    MyReader() {
        super(new InputStreamReader(System.in));
    }

    char next() {
        if (head == tail) {
            try {
                tail = super.read(cbuf, 0, cbuf.length);
            } catch (IOException e) {
                e.printStackTrace();
            }
            head = 0;
        }
        return cbuf[head++];
    }

    void back() {
        head--;
    }

    boolean minus() {
        boolean minus;
        while (true) {
            char c = next();
            if (!isDelimiter(c)) {
                if (!(minus = c == '-')) back();
                return minus;
            }
        }
    }

    void skip() {
        while (isDelimiter(next()));
        back();
    }

    char[] s(int N) {
        char[] cbuf = new char[N];
        read(cbuf, 0, N);
        return cbuf;
    }

    public int read(char[] cbuf, int off, int len) {
        skip();
        int i;
        for (i = 0; i < cbuf.length; i++) {
            char c = next();
            if (isDelimiter(c)) {
                break;
            }
            cbuf[i] = c;
        }
        return i;
    }

    boolean isDelimiter(char c) {
        return c == ' ' || c == '\n' || c == '\r';
    }

    int i() {
        boolean minus = minus();
        int n = 0;
        while (true) {
            int k = next() - '0';
            if (k < 0 || 9 < k) break;
            n = 10 * n + k;
        }
        return minus ? -n : n;
    }

    int[] ii(final int N) {
        int[] a = new int[N];
        for (int j = 0; j < a.length; j++) a[j] = i();
        return a;
    }

    long l() {
        boolean minus = minus();
        long n = 0;
        while (true) {
            int k = next() - '0';
            if (k < 0 || 9 < k) break;
            n = 10 * n + k;
        }
        return minus ? -n : n;
    }
}


Measured memory_bytes: 36000
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def read():
    X, Y = list(map(int, input().strip().split()))
    return X, Y


def solve(X, Y):
    if 4 * X == Y:
        return "Yes"
    elif 2 * X == Y:
        return "Yes"
    else:
        b = (Y - 2 * X) // 2
        a = X - b
        if a > 0 and b > 0 and a + b == X and 2 * a + 4 * b == Y:
            return "Yes"
    return "No"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 9224
#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int x,y;
    cin>>x>>y;
    int temp=(y-(2*x))/2;
    if((y-(2*x))%2==0&&temp>=0&&temp<=x)
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }

return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <ctype.h>

using namespace std;

char get_type(string s)
{
	if (islower(s[0]))
		return s.find('_') != -1 ? 'D' : 'L';
	else
		return 'U';
}

vector<string> split_d(string s)
{
	vector<string> v;
	int p;
	for (; (p = s.find('_')) != -1; )
	{
		if (p > 0) v.push_back(s.substr(0, p));
		s = s.substr(p + 1);
	}
	if (!s.empty()) v.push_back(s);
	return v;
}

vector<string> split_c(string s)
{
	s[0] = tolower(s[0]);

	vector<string> v;
	for (int i = 0; i < s.length();)
	{
		if (isupper(s[i]))
		{
			string t = s.substr(0, i);
			v.push_back(t);
			s = s.substr(i);
			s[0] = tolower(s[0]);
			i = 0;
		}
		else
		{
			i++;
		}
	}
	if (!s.empty()) v.push_back(s);
	return v;
}

string make_d(vector<string> v)
{
	string s = "";
	for (int i = 0; i < v.size(); i++)
	{
		if (i != 0) s += "_";
		s += v[i];
	}
	return s;
}

string make_c(vector<string> v, bool upper_camel)
{
	string s = "";
	for (int i = 0; i < v.size(); i++)
	{
		if (i != 0 || upper_camel) v[i][0] = toupper(v[i][0]);
		s += v[i];
	}
	return s;
}

int main()
{
	string s;
	char c;
	for(;cin>>s>>c, c!='X';)
	{
		char type = get_type(s);

		vector<string> v;

		switch (type)
		{
		case 'L':
		case 'U':
			v = split_c(s);
			break;
		case 'D':
			v = split_d(s);
			break;
		}
		switch (c)
		{
		case 'L':
			cout << make_c(v, false);
			break;
		case 'U':
			cout << make_c(v, true);
			break;
		case 'D':
			cout << make_d(v);
			break;
		}
		cout << endl;
	}
	return 0;
}

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

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

int main() {

	bool a[10] = { false };

	for (int i = 0; i < 4; i++) {
		int tmp;
		cin >> tmp;
		a[tmp] = true;
	}

	if (a[1] && a[4] && a[7] && a[9])
		cout << "YES";
	else
		cout << "NO";
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
# 最大公約数(mathは3.5以降) 
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

# 初期入力
import sys
#input = sys.stdin.readline  #文字列では使わない
N,X = map(int, input().split())
x = list(map(int, input().split()))

# ｘの隣同士の距離リスト
x_div =[abs(X-x[0])] #初項
for i in range(N-1):
    x_div.append(abs(x[i] -x[i+1]))

#x_divの最大公約数
if N ==1:
    ans =abs(x[0] -X)
else:
    ans =gcd_list(x_div)
print(ans)

Measured memory_bytes: 20408
#include<bits/stdc++.h>
using namespace std;
long long a[505],b[505];
int s[505][505],f[505][505];
int n,m,l,x,y;
int main()
{
//    freopen("express.in","r",stdin);
//    freopen("express.out","w",stdout);
    scanf("%d%d%d",&n,&m,&l);
    for(register int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x]++;
        b[y]++;
        s[x][y]++;
        f[y][x]++;
    }
    for(register int i=500;i>=1;i--)
        a[i]=a[i]+a[i+1];
    for(register int i=1;i<=500;i++)
        b[i]=b[i]+b[i-1];
    for(register int i=1;i<=500;i++)
        for(register int j=i+1;j<=500;j++)
            s[i][j]+=s[i][j-1];
    //for(register int i=1;i<=500;i++)
    //    for(register int j=i;j>=1;j--)
    //        f[i][j]+=f[i][j+1];
    for(register int i=1;i<=500;i++)
        for(register int j=i-1;j>=1;j--)
            s[j][i]+=s[j+1][i];
    for(register int i=1;i<=l;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",s[x][y]);
    }
    return 0;
}

Measured memory_bytes: 2944
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}



int[] readints() {
    return readln.split.map!(to!int).array;
}

void main() {
    string s;
    while ((s = readln.chomp) != null) {
        auto ab = s.split.map!(to!int).array;
        int a = ab[0], b = ab[1];

        writeln(gcd(a, b));
    }
}

Measured memory_bytes: 2392
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
  int N, K;
  std::cin >> N >> K;
  std::vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    std::cin >> A[i];
  }
  std::sort(A.begin(), A.end());
  std::cout << std::accumulate(A.begin(), A.begin() + K, 0) << std::endl;
  return 0;
}


Measured memory_bytes: 3600
import sys
from bisect import *
from collections import deque
pl=1
#from math import *
from copy import *
#sys.setrecursionlimit(10**6)
if pl:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('outpt.txt','w')

def li():
	return [int(xxx) for xxx in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	

def find(i):
	if i==a[i]:
		return i
	a[i]=find(a[i])
	return a[i]
def union(x,y):
	xs=find(x)
	ys=find(y)
	if xs!=ys:
		if rank[xs]<rank[ys]:
			xs,ys=ys,xs
		rank[xs]+=1
		a[ys]=xs		
t=1
while t>0:
	t-=1
	n,m=mi()
	a=[i for i in range(n+1)]	
	rank=[0 for i in range(n+1)]			
	for i in range(m):
		x,y=mi()
		union(x,y) 
	s=set()	
	for i in range(1,n+1):
		a[i]=find(i)
		s.add(a[i])
	print(len(s)-1)	




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

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

using namespace std;

typedef long long int lli;
typedef vector<int> vi;

int main() {
	int a, b;

	cin >> a >> b;

	cout << a + b / 2;


	return 0;
}

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

void reverse(std::string& str)
{
	size_t N = str.size();
	for (size_t i = 0; i < N/2; ++i)
		std::swap(str[i], str[N - 1 - i]);
}

int main() {
	int M;
	string s;
	string half1,half2,temp;
	int count,R1,R2,equal;
	vector<string> train;


	cin >> M;

	for (int i=0;i<M;i++) {
		train.clear();
		cin >> s;
		count = 0;

		for(int j=1;j<s.length();j++) { //??????????????????????±????
			half1 = "";
			half2 = "";
			for (int t=0;t<j;t++) {
				half1 += s[t]; //???????????????????????????	
			}
			for(int k=0;k<s.length()-j;k++) {
				half2 += s[j+k]; //??????????????????????????????
			}
			for (int p=0; p<2; p++) {
				if (p == 1) {
					temp = half1;
					half1 = half2;
					half2 = temp;
				}

				for(int t=0;t<4;t++) {
					equal = 0;

					if(t > 0) {
						reverse(half1);
					}
					if(t == 2) {
						reverse(half2);
					}	

					for(int l=0; l<train.size(); l++) {
						if (train[l] == half1+half2) {
							equal = 1;
						}
					}
					if (equal == 0) {
					train.push_back(half1+half2);
					}
					//cout << half1+half2 << endl;
				}

			}
			
			
			
		}
		cout << train.size() << endl;
	}
}

Measured memory_bytes: 3132
#include<bits/stdc++.h>
using namespace std;
const int offset=100000;
int n,a[100005],s[1000050],bit[1000050];
int lowb(int x)
{
	return x&(-x);
}
void add(int x)
{
	while(x<=2*offset)
	{
		bit[x]++;
		x+=lowb(x);
	}
}
long long cal(int x)
{
	long long ans=0;
	while(x>=1)
	{
		ans+=bit[x];
		x-=lowb(x);
	}
	return ans;
}
bool check(int x)
{
	memset(bit,0,sizeof(bit));
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+(a[i]>=x?1:-1);
	long long sum=0;
	for(int i=0;i<=n;i++)
	{
		sum+=cal(s[i]+offset);
		add(s[i]+offset);
	}
	return sum>=1LL*n*(n+1)/4;
}
int main()
{
	cin>>n;
	int l=0,r=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		r=max(r,a[i]);
	}
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	cout<<r<<endl;
	return 0;
}


Measured memory_bytes: 8448
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      	String s = sc.next();
      	
      	switch(s){
          case "SUN":
            System.out.println(7);
            break;
          case "MON":
            System.out.println(6);
            break;
          case "TUE":
            System.out.println(5);
            break;
          case "WED":
            System.out.println(4);
            break;
          case "THU":
            System.out.println(3);
            break;
          case "FRI":
            System.out.println(2);
            break;
          case "SAT":
            System.out.println(1);
            break;
        }
    }
}

Measured memory_bytes: 35456
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}

var mod int

func main() {
	mod = 1000000007
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n, w := intScanner(), intScanner()
	x, v := intScanner(), intScanner()
	zero := []int{v}
	one := make([]int, 0, n)
	two := make([]int, 0, n)
	three := make([]int, 0, n)
	for i := 1; i < n; i++ {
		y := intScanner()
		if y == x {
			zero = append(zero, intScanner())
		} else if y == x+1 {
			one = append(one, intScanner())
		} else if y == x+2 {
			two = append(two, intScanner())
		} else if y == x+3 {
			three = append(three, intScanner())
		}
	}
	sort.Sort(sort.Reverse(sort.IntSlice(zero)))
	sort.Sort(sort.Reverse(sort.IntSlice(one)))
	sort.Sort(sort.Reverse(sort.IntSlice(two)))
	sort.Sort(sort.Reverse(sort.IntSlice(three)))
	for i := 1; i < len(zero); i++ {
		zero[i] = zero[i-1] + zero[i]
	}
	for i := 1; i < len(one); i++ {
		one[i] = one[i-1] + one[i]
	}
	for i := 1; i < len(two); i++ {
		two[i] = two[i-1] + two[i]
	}
	for i := 1; i < len(three); i++ {
		three[i] = three[i-1] + three[i]
	}
	ans := 0
	for i := 0; i <= len(zero); i++ {
		for j := 0; j <= len(one); j++ {
			for k := 0; k <= len(two); k++ {
				for l := 0; l <= len(three); l++ {
					s := x*i + (x+1)*j + (x+2)*k + (x+3)*l
					if s <= w {
						z := 0
						if i > 0 {
							z += zero[i-1]
						}
						if j > 0 {
							z += one[j-1]
						}
						if k > 0 {
							z += two[k-1]
						}
						if l > 0 {
							z += three[l-1]
						}
						ans = larger(ans, z)
					}
				}
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1788
n = int(input())
p = list(map(int , input().split()))
cnt = 0
for i in range(1,n - 1):
    if p[i-1] < p[i] and p[i] < p[i + 1] or p[i - 1] > p[i] and p[i] > p[i + 1]:
        cnt += 1
print(cnt)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define poly vector<ll>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
inline ll read(){
	ll x=0;char ch=getchar();bool d=1;
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') d=0;
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return d?x:-x;
}
inline void write(ll x){
	if(x<0) x=-x,putchar('-');
	if(x>=10) write(x/10);
	putchar('0'+x%10);
}
inline void writeln(ll x){write(x);puts("");}
inline void writep(ll x){write(x);putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=1e5+5,mo=1e9+7;
int f[N],a[N];
int ksm(int x,int p){
	int res=1;
	for(;p;p>>=1,x=(ll)x*x%mo){
		if(p&1) res=(ll)res*x%mo;
	}
	return res;
}
int main(){
	int n=read(),m=read(),k=0;
	for(int i=1;i*i<=n;i++){
		if(n%i==0){
			a[++k]=i;
			if(i*i!=n) a[++k]=n/i;
		}
	}
	sort(a+1,a+k+1);
	int ans=0;
	For(i,1,k){
		f[i]=ksm(m,(a[i]+1)/2);
		For(j,1,i-1){
			if(a[i]%a[j]==0) f[i]=(f[i]-f[j]+mo)%mo;
		}
		if(a[i]&1) ans=(ans+(ll)f[i]*a[i])%mo;
		else ans=(ans+(ll)f[i]*a[i]/2)%mo;
	}
	cout<<ans;
}

Measured memory_bytes: 3644