akhauriyash/Code-Regression huggingface dataset:
from itertools import product

class ACS:
    def __init__(self, D, C, S):
        self.now = 1
        self.D = D
        self.satisfaction = 0
        self.sat_log = []
        self.C = C
        self.S = S
        self.last = [0]*26
    
    def hold_contest(self, T):
        self.satisfaction += self.S[self.now-1][T]
        self.last[T] = self.now

        for i in range(26):
            self.satisfaction -= self.C[i]*(self.now - self.last[i])
        
        self.sat_log.append(self.satisfaction)
        self.now += 1
    
    def choice_max(self):
        maxs, maxi = -(10**18), 0
        for i in range(26):
            s = self.score_check(i)
            if s >= maxs:
                maxs = s
                maxi = i
        return maxi

    def nd_choice_max(self, n):
        maxs, maxi = -(10**18), (0 for _ in range(n))
        for s in product(range(26), repeat=n):
            score = self.nd_score_check(s)
            if score >= maxs:
                maxs = score
                maxi = s
        return maxi



    def score_check(self, T):
        score = self.satisfaction + self.S[self.now-1][T]

        for i in range(26):
            if i != T:
                score -= self.C[i]*(self.now - self.last[i])
        return score

    def nd_score_check(self, Ts: list):
        last = self.last[::]
        score = self.satisfaction
        d = self.now
        # print(d)
        
        for T in Ts:
            score += self.S[d-1][T]
            last[T] = d
            for i in range(26):
                score -= self.C[i]*(d - last[i])
            d += 1
        return score

        

    def _log(self):
        print(f"\nday {self.now}\n satisfaction: {self.satisfaction}")

        


D = int(input())
C = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for _ in range(D)]
n = 3

acs = ACS(D, C, S)

for d in range(D//n):
    next_contests = acs.nd_choice_max(n)
    
    for c in next_contests:
        acs.hold_contest(c)
        print(c+1)
    
next_contests = acs.nd_choice_max(D%n)
for c in next_contests:
    acs.hold_contest(c)
    print(c+1)

Measured memory_bytes: 69584
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) { a = b; return 1;} return 0;}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) { a = b; return 1;} return 0;}
#define dame {cout<< "-1" <<"\n"; return;}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
#define PI (acos(-1))
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------
ll modpow(ll a, ll n=MOD-2, ll mod=MOD){ // a^n % MOD の計算
    ll res = 1;
    while (n > 0){
        if(n & 1) res = res * a % mod;
        a = a * a  % mod;
        n >>= 1;
    }
    return res;
}
struct edge{ll to;};
struct graph{
    ll N;
    vector<vector<edge> > G;
    vector<bool> used;
    vector<vector<ll>> bubunode;

    graph(ll n): N(n), G(N), used(N,false), bubunode(N){}

    void add_edge(ll s, ll t){
        G[s].emplace_back((edge){t});
        G[t].emplace_back((edge){s}); //無向ならON
    }

    ll dfs(ll v=0){
        used[v]=true;
        ll ct=1;
        for(auto E : G[v]){
            if(!used[E.to]){
                ll x=dfs(E.to);
                bubunode[v].emplace_back(x);
                ct+=x;
            }
        }
        ll y=N-ct;
        if(y>0) bubunode[v].emplace_back(y);
        return ct;
    }
};

//--MAIN-----------------------------------
void Main() {
    ll N; cin>>N;
    graph g(N);
    rep(i,N-1){
        ll a,b; cin>>a>>b;
        g.add_edge(--a,--b);
    }
    g.dfs();
    ll ans=0;
    ll ans3=modpow(2,N-1)-1;
    rep(i,N){
        auto& ve=g.bubunode[i];
        if(ve.size()<=1) continue;
        ll ans2=ans3;
        for(auto& x: ve){
            ans2-=modpow(2,x)-1;
            ans2+=MOD;
            ans2%=MOD;
        }
        ans+=ans2;
        ans%=MOD;
    }
    ll gya=modpow(2,N);
    gya=modpow(gya);
    ans*=gya;
    ans%=MOD;
    cout<< ans <<"\n";
}

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


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

long long n, a;
vector<long long> x;
long long dp[55][55][2555] = {0};

long long solve();

int main() {
  cin >> n >> a;
  for(int i = 0; i < n; ++i) {
    int nx;
    cin >> nx;
    x.push_back(nx);
  }
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long ans = 0;
  for(int i = 0; i < n; ++i) {
    int now = x[i];
    if(i != 0)
      for(int j = 1; j <= i + 1; ++j)
        for(int k = 0; k <= 2550; ++k)
          dp[i][j][k] = dp[i - 1][j][k];
    dp[i][1][now] += 1;
    if(i != 0)
      for(int j = 1; j <= i + 1; ++j)
        for(int k = 0; k + now <= 2550; ++k) {
          dp[i][j][k + now] += dp[i - 1][j - 1][k];
        }
  }
  for(int i = 1; i <= n; ++i) {
    ans += dp[n - 1][i][i * a];
  }
  return ans;
}


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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define int long long

typedef pair<int, int> ii;

const int mod = 1e9 + 7;

int dp[105][15], w, h, k, pw[105], num[105];

signed main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> h >> w >> k;
    pw[0] = 1;
    for(int i = 1; i <= 100; i++)
        pw[i] = (1ll * pw[i - 1] * 2) % mod;
    dp[h][1] = 1;
    for(int l = 1; l <= 8; l++) {
        for(int i = 0; i < (1 << l); i++) {
            int ok = 0;
            for(int j = 0; j < l - 1; j++) {
                if(((1 << j) & i) && ((1 << (j + 1)) & i))
                    ok = 1;
            }
            num[l] += (1 - ok);
            num[l] %= mod;
        }
    }
    num[0] = 1;
    for(int i = h; i >= 1; i--) {
        for(int j = 1; j <= w; j++) {
            if(!dp[i][j]) continue;
            int sum = w - j - 2;
            int sum1 = w - j - 1;
            int sum2 = j - 2;
            dp[i - 1][j + 1] += (1ll * dp[i][j] * num[max(sum, 0ll)] * num[max(sum2, 0ll)]) % mod;
            dp[i - 1][j - 1] += (1ll * dp[i][j] * num[max(sum1, 0ll)] * num[max(j - 3, 0ll)]) % mod;
            dp[i - 1][j] += (1ll * dp[i][j]  * num[max(sum2, 0ll)] * num[max(sum1, 0ll)]) % mod;
            dp[i - 1][j + 1] %= mod;
            dp[i - 1][j - 1] %= mod;
            dp[i - 1][j] %= mod;
        }
    }
    cout << dp[0][k] % mod << "\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define ll long long
#define MOD (ll)1e9+7

const ll INF= 1LL << 60;

//入力
int N;
vector<double> p;

//dp
long double dp[3010][3010];

void add(ll& a,ll b){
  a+=b;
  if(a>=MOD) a-=MOD;
}
 
int main(){
  cin>> N;
  
  for(int i=0;i<N;i++){
    double pi;
    cin>>pi;
    p.push_back(pi);
  }
  
  for(int i=0;i<=N;i++)
    for(int j=0;j<=N;j++)
      dp[i][j]=0;
  
  dp[0][0]=1;

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      dp[i+1][j+1]+=dp[i][j]*p[i];//i枚目に表が出たとき
      dp[i+1][j]+=dp[i][j]*(1-p[i]);//i枚目に裏が出たとき
    }
  }
  /*
  for(int i=0;i<=N;i++){
    for(int j=0;j<=N;j++){
      cout << dp[i][j] << " ";
    }
    cout<<endl;
  }
  */
  
  //表の枚数が裏の枚数を上回る確率
  double ans=0;
  for(int j=(N+1)/2;j<=N;j++){
    ans+=dp[N][j]; 
  }
  
  //相対誤差が1e-9以下でないといけないため，小数点以下10桁を表示
  cout <<  fixed << setprecision(10)<< ans << endl;
  
}

Measured memory_bytes: 141568
A, B, K = map(int,input().split())
left = A + K - 1
right = B - K + 1
if left < right:
    for i in range(A, left + 1):
        print(i)
    for i in range(right, B + 1):
        print(i)
else:
    for i in range(A, B + 1):
        print(i)

Measured memory_bytes: 3060
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)

	writer := bufio.NewWriter(os.Stdout)

	s := getNextString(scanner)
	n := len(s)
	nn := make([]int, n)
	for i := 0; i < n; i++ {
		nn[i] = int(s[i] - '0')
	}

	ans := 0
	for bits := 0; bits < 1<<uint(n-1); bits++ {
		for i := 0; i < n; i++ {
			num := nn[i]
			for b := 1 << uint(n-2-i); b&bits == 0 && b > 0; b >>= 1 {
				num *= 10
			}
			ans += num
		}
	}

	fmt.Fprintln(writer, ans)

	writer.Flush()
}


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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)

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

int main(void) {
    int n,x;
    vector<int> vc,vt;
    cin >>n;
    REP(i,n){
        cin >>x;
        vc.push_back(x);
        vt.push_back(x);
    }
    sort(vc.begin(),vc.end());
    REP(i,n){
        if(vt[i]<vc[n/2]){
            cout << vc[n/2] << endl;
        }else{
            cout << vc[n/2-1] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3948
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    string s;
   cin >> s;
   for(int i = 0; i < s.size(); i++){
       if(s[i] + n <= 'Z')
       cout << char(s[i] + n);
       else
       cout << char(s[i] + n - ('Z' - 'A' + 1));
   }
   cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,i;
string a;

int main(){
    cin>>n;
    for(i=n;i<1000;i++){
        if((i/100)==((i%100)/10)&&(i/100)==(i%10))break;
    }
    cout<<i<<endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<vector>
#include<string>
using namespace std;
#define l long long
#define pb push_back
#define mem(a,n) memset(a,n,sizeof(a))
//#define find(v,n) find(v.begin(),v.end(),n)
#define sort1(v) sort(v.begin(),v.end())
#define lb(v,n) lower_bound(v.begin(),v.end(),n)-v.begin()
//#define ub(v,n) upper_bound(v.begin(),v.end(),n)-v.begin()
#define mod 1000000007
#define reverse(s) reverse(s.begin(),s.end())
//#define pi pair<l,l> 
const double pi=3.141592653589793;
bool isprime(l n)
{
	for(l i=2;i*i<=n;i++)
	{
		if(n%i==0)
			return false;
	}
	return true;
}
/*bool fact(l n)
{
	vector<l> v;
	for(l i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			if(i%2==1||(n/i)%2==1)
			{
				return true;
			}
		}
	}
	return false;
}*/
l power(l a,l b)
{
	l ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans=(ans*a)%mod;
		}
		b>>=1;
		a=(a*a)%mod;
	}
	return ans%mod;
}//prefixsums
l ncr(l n,l r,vector<l> fact)
{
	l ans=(fact[n]/((fact[n-r]*fact[r])%mod))%mod;
	return ans;
}
void frooty(l t)
{
	string s;
	cin>>s;
	l ans=0;
	for(l i=0;i<s.size();i++)
	{
		ans=(ans+s[i]-'0')%9;
	}
	if(ans==0)
		cout<<"Yes"<<"\n";
	else
		cout<<"No"<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int q=1;
	//cin>>q;
	//q++;
	for(int i=0;i<q;i++)
	{
		char c[]="anudeep";
		frooty(i+1);
	}
}

Measured memory_bytes: 3776
#![allow(unused_imports)]

use std::{i32, i64, u32, u64, usize, f64};
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::io::{stdout, Write, BufWriter};
use std::mem::{swap};
use maplit::*;
use proconio::{input, marker::{Isize1, Usize1, Bytes, Chars}};

#[proconio::fastout]
fn main() {
    input!(
        core: Chars,
        n: usize,
    );
    let mut s = VecDeque::with_capacity(core.len() + n);
    for c in core { s.push_back(c); }
    let mut rev = 0;
    for _ in 0..n {
        input!(mode: u8);
        if mode == 1 { rev = 1 - rev; }
        else {
            input!(lr: u8, c: char,);
            if (lr - 1) ^ rev == 0 { s.push_front(c); }
            else { s.push_back(c); }
        }
    }
    if rev == 0 { println!("{}", s.into_iter().collect::<String>()) }
    else { println!("{}", s.into_iter().rev().collect::<String>()) }
}


Measured memory_bytes: 4720
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

#define MAX 2500
signed main() {
	static bool dp[52][MAX][MAX] = {};
	dp[0][0][0] = true;
	int N; cin >> N;
	vector<int> T(N); rep(i, 0, N) { cin >> T[i]; }
	int sum = accumulate(T.begin(), T.end(), 0);
	rep(i, 0, N)rep(j, 0, MAX / 2)rep(k, 0, MAX / 2) {
		if (!dp[i][j][k])continue;
		dp[i + 1][j + T[i]][k] = dp[i][j][k];
		dp[i + 1][j][k + T[i]] = dp[i][j][k];
		dp[i + 1][j][k] = dp[i][j][k];
	}
	int ans = INF;
	rep(j, 0, MAX / 2)rep(k, 0, MAX / 2) {
		if (dp[N][j][k]) {
			ans = min(ans, max({ j, k, sum - j - k }));
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 95096
#include<iostream>
#include<istream>
#include<algorithm>
#include<string>
using namespace std;

int main(){
	string apple,peach,before,after,sen;
	apple ="apple";
	peach ="peach";

	getline(cin,sen);

	for(int i=0;i<=sen.size()-5;i++){
		
		if(sen[i]=='a' && sen[i+1]=='p' && sen[i+2]=='p' && sen[i+3]=='l' && sen[i+4]=='e'){
			before =sen.substr(0,i);
			after  =sen.substr(i+5);
			sen = before + peach + after;
		}else if(sen[i]=='p' && sen[i+1]=='e' && sen[i+2]=='a' && sen[i+3]=='c' && sen[i+4]=='h'){
			before =sen.substr(0,i);
			after  =sen.substr(i+5);
			sen = before + apple + after;
		}
	}
	cout<<sen<<endl;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int level[25][25];
int visited[25][25];
int fx[]={0,1,0,-1};
int fy[]={1,0,-1,0};
int r,c;
int bfs(int x, int y, string s[])
{
    queue<pair<int,int>>q;
    q.push(make_pair(x,y));
    visited[x][y]=-1;
    int temp=0;
    for(;!q.empty();)
    {
        pair<int,int>p;
        p=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int g=p.first+fx[i];
            int h=p.second+fy[i];
            if(visited[g][h]==0 && g>=0 && g<r && h>=0 && h<c && s[g][h]=='.')
            {
                visited[g][h]=-1;
                level[g][h]=level[p.first][p.second]+1;
                q.push(make_pair(g,h));
                temp=max(temp,level[g][h]);
            }
        }
    }
    return temp;
}
int main()
{
    int i,j;
    cin>>r>>c;
    string s[r+1];
    for(i=0;i<r;i++)
        cin>>s[i];
    int ans=0;
    for(i=0;i<r;i++)
    {
        for(j=0;j<c;j++)
        {
            if(s[i][j]=='.')
            {
                memset(visited,0,sizeof(visited));
                memset(level,0,sizeof(level));
                ans=max(ans,bfs(i,j,s));
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


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

using namespace std;

typedef long long ll;

int N,K;
ll L,R;
ll a[41];

ll bitsum(int b, int offset) {
  ll s = 0;
  for (int i=1; b>0; b>>=1,i+=1) {
    if (b & 1) {
      s += a[offset+i];
    }
  }
  return s;
}

ll solve() {
  int M = N/2;
  vector<vector<ll>> h(M+1);
  for (int i=0; i<(1<<M); ++i) {
    int bc = __builtin_popcount(i);
    h[bc].push_back(bitsum(i, 0));
  }
  for (int i=1; i<=M; ++i) {
    sort(h[i].begin(), h[i].end());
  }
  ll ans = 0;
  for (int i=0; i<(1<<(N-M)); ++i) {
    ll s = bitsum(i, M);
    int bc = __builtin_popcount(i);
    if (K<bc || K-bc>M) {
      continue;
    }
    ans += upper_bound(h[K-bc].begin(), h[K-bc].end(), R-s) - lower_bound(h[K-bc].begin(), h[K-bc].end(), L-s);
  }
  return ans;
}

int main() {
  cin>>N>>K>>L>>R;
  for (int i=0; i<N; ++i) {
    cin>>a[i+1];
  }
  cout<<solve()<<endl;
  return 0;
}


Measured memory_bytes: 12212
import java.util.Scanner;

//AtCoder Beginner Contest 150
//B - Count ABC
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = Long.parseLong(sc.next());
		String S = sc.next();
		sc.close();

		long ans = 0;
		for (int i = 0; i < S.length()-2; i++) {
			if (S.charAt(i) == 'A' && S.charAt(i+1) == 'B' && S.charAt(i+2) == 'C') {
				ans++;
			}
		}

		System.out.println(ans);
	}
}


Measured memory_bytes: 23252
#include <math.h>

#include <algorithm>  //sort,二分探索,など
#include <array>
#include <bitset>         //固定長bit集合
#include <cmath>          //pow,logなど
#include <complex>        //複素数
#include <deque>          //両端アクセスのキュー
#include <functional>     //sortのgreater
#include <iomanip>        //setprecision(浮動小数点の出力の誤差)
#include <iostream>       //入出力
#include <map>            //map(辞書)s
#include <numeric>        //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>          //キュー
#include <set>            //集合
#include <stack>          //スタック
#include <string>         //文字列
#include <unordered_map>  //イテレータあるけど順序保持しないmap
#include <unordered_set>  //イテレータあるけど順序保持しないset
#include <utility>        //pair
#include <vector>         //可変長配列

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()  // sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())  // sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main() {
  cout << fixed << setprecision(15);
  int r;
  cin >> r;
  cout << M_PI * 2 * r << endl;
  return 0;
}


Measured memory_bytes: 3788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int N,K; cin >> N >> K; string S; cin >> S;
   int cnt = 0;
  for(int i = 0; i < N-1; i++){ if(S[i] == S[i+1]){ cnt++;}}
  
  cout << min(cnt + 2*K, N-1) << endl; return 0;}

Measured memory_bytes: 512
MARCH = {'M':0,'A':0,'R':0,'C':0,'H':0}
N=int(input())
for i in range(N):
  s=str(input())
  if s[0]=='M':
    MARCH['M']+=1
  elif s[0]=='A':
    MARCH['A']+=1
  elif s[0]=='R':
    MARCH['R']+=1
  elif s[0]=='C':
    MARCH['C']+=1
  elif s[0]=='H':
    MARCH['H']+=1
ans = MARCH['M']*MARCH['A']*MARCH['R']\
  +MARCH['M']*MARCH['A']*MARCH['C']\
  +MARCH['M']*MARCH['A']*MARCH['H']\
  +MARCH['M']*MARCH['R']*MARCH['C']\
  +MARCH['M']*MARCH['R']*MARCH['H']\
  +MARCH['M']*MARCH['C']*MARCH['H']\
  +MARCH['A']*MARCH['R']*MARCH['C']\
  +MARCH['A']*MARCH['R']*MARCH['H']\
  +MARCH['A']*MARCH['C']*MARCH['H']\
  +MARCH['R']*MARCH['C']*MARCH['H']
print(ans)

Measured memory_bytes: 9184
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ll n,w1;
  cin >>n>>w1;
  ll w[n+1],v[n+1];
  for(ll i=1;i<=n;i++){
    cin >> w[i]>>v[i];
  }
  ll dp[n+1][w1+1];
  for(ll i=0;i<n+1;i++){
    for(ll j=0;j<w1+1;j++){
      dp[i][j]=-1;
    }
  }
  for(ll i=0;i<w1+1;i++){
     dp[0][i]=0;
  }
  for(ll i=1;i<n+1;i++){
    for(ll j=0;j<w1+1;j++){
      if(j-w[i]<0) dp[i][j]=dp[i-1][j];
      else dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);
    }
    }
  cout << dp[n][w1]<<endl;
  return 0;
}


Measured memory_bytes: 79104
#include<iostream>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
long long ans;
struct node{
	long long int a,b;
}e[100005];
bool cmp(node x,node y)
{
	return x.a<y.a;
}
inline long long read()
{
	long long x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    	e[i].a=read(),e[i].b=read();
    }
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
    	if(e[i].b<=m)
    	{
    		ans+=e[i].b*e[i].a;
    		m-=e[i].b;
 //   		cout<<ans<<"'"<<m<<endl;
    	}
    	else
    	{
    		ans+=e[i].a*m;
    		m=0;
    	}
    	if(m==0)
    	{
    		break;
    	}
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<stack>

#include<string>
#include<map>
using namespace std;

int main(){
  int N,Q;
  string eraname;
  int basedy,westy;
  while(cin >> N >> Q && (N!=0 || Q!=0)){
    string nams[10010];
    int begin[N],end[N];
    for(int i=0;i<N;i++){
      cin >> eraname >> basedy >> westy;
      nams[i]=eraname;
      begin[i]=westy-basedy;
      end[i]=westy;
    }
    for(int i=0;i<Q;i++){
      cin >> westy;
      for(int j=0;j<N;j++){
	if(westy > begin[j] && westy <=end[j]){
	  cout << nams[j] << " " <<  westy-begin[j] <<endl;
	  break;
	}
	if(j==N-1){
	  cout << "Unknown" << endl;
	}
      }
    }
  }

}

Measured memory_bytes: 1352
import itertools
n = int(input())
m = []
for i in range(n):
    x,y = map(int,input().split())
    m.append((x,y))
check = list(itertools.permutations([i for i in range(n)]))
ans = 0
for i in check:
    for c,j in enumerate(i):
        if c == n-1:
            continue
        ans += ((m[j][0]-m[i[c+1]][0])**2+(m[j][1]-m[i[c+1]][1])**2)**0.5
for i in range(1,n+1):
    ans/=i
print(ans)

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

int main(){

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

  int ans = x[K-1] - x[0] + min(abs(x[0]), abs(x[K-1]));
  for(int j=0;j<N-K+1;j++){
    ans = min(ans, x[j+K-1] - x[j] + min(abs(x[j]), abs(x[j+K-1])));
  }
  cout << ans;
}

Measured memory_bytes: 640
import Data.Array
import Data.List 

main = print =<< sol <$> get <*> get

get = fmap read . words <$> getLine

sol [n,m] as = s + (m-c)*lvl
  where
  a = listArray (1,n) $ sortBy (flip compare) as
  fnd a x = bsearch (0,n) ((x <=) . (a!))
  cnt a x = sum $ fnd a . (-) x <$> elems a
  lvl = bsearch (2*a!n,2*a!1) ((m <=) . cnt a)
  i = fnd a (lvl - a!1)
  acc = array (1,n) $ (1,a!1):[(i,a!i + acc!(i-1)) | i <- [2..n]]
  (c,s) = foldl' upd (0,0) [1..i]
  upd (c,s) i = (c+j, s + j*(a!i) + acc!j)
    where j = fnd a (lvl - a!i)

-- | Binary search
bsearch :: (Int, Int) -> (Int -> Bool) -> Int
bsearch (l,r) p -- precondition: (p l) && not (p r)
  | l >= r    = l
  | p m       = bsearch (m,r) p
  | otherwise = bsearch (l,m-1) p
  where m = (l+r+1) `div` 2


Measured memory_bytes: 67964
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int k; cin >> k;
  ll ans = 0;
  FOR(a, 1, k + 1) FOR(b, 1, k + 1) FOR(c, 1, k + 1) {
    ans += gcd(gcd(a, b), c);
  }
  cout << ans << '\n';
  return 0;
}


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

int main() {
  
  double n,d,x,y,kyori;
  cin >> n >> d;
  
  int cnt = 0;
  
  for ( int i = 0; i < n; i++){
    cin >> x >> y;
    kyori = sqrt(x * x + y * y);
    if ( kyori <= d ){
      cnt++;
    }
  }
  
  cout << cnt << endl;  
  
}

Measured memory_bytes: 3772
#include <bits/stdc++.h>
#define ll long long
using namespace std;
pair<int,int> cal(int x) {
	int a=x%10,b;
	while(x) {
		b=x;
		x/=10;
	}
	return {a,b};
}
map<pair<int,int>,int> ma;
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		ma[cal(i)]++;
	}
	ll ans=0;
	for(int i=1;i<=n;i++) {
		auto it=cal(i);
		ans+=ma[{it.second,it.first}];
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using static Assistant.Input;
using static Assistant.Debug;
using System.Linq;
using Assistant;
using System.Text;

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

            StringBuilder sb = new StringBuilder();
            
            for (int i = 0; i < T.Length; i++)
            {
                if (T[i] == '?') sb.Append('D');
                else sb.Append(T[i]);
            }

            Console.WriteLine(sb);

        }


    }


}

namespace Assistant
{
    static class Input
    {
        static List<string> line = new List<string>();
        static int index = 0;
        static String RNext()
        {
            if (line.Count <= index) line.AddRange(Console.ReadLine().Split());
            return line[index++];
        }
        public static int RInt => int.Parse(RNext());
        public static long RLong => long.Parse(RNext());
        public static int[] RInts => Console.ReadLine().Split().Select(int.Parse).ToArray();
        public static long[] RLongs => Console.ReadLine().Split().Select(long.Parse).ToArray();
        public static string RString => RNext();
        //以下未テスト
        public static int[] RIntsC(int c) => Enumerable.Repeat(0, c).Select(x => int.Parse(RNext())).ToArray();
        public static long[] RLongsC(int c) => Enumerable.Repeat(0, c).Select(x => long.Parse(RNext())).ToArray();
        public static char[][] RMap(int h) => Enumerable.Repeat(0, h).Select(x => Console.ReadLine().ToCharArray()).ToArray();
    }

    static class Debug
    {
        static public void Draw2D<T>(T[,] map, int mode = 1)
        {
#if DEBUG
            int W = map.GetLength(0);
            int H = map.GetLength(1);

            T[,] map2 = new T[W + 1, H + 1];
            for (int i = 0; i < W + 1; i++)
            {
                for (int j = 0; j < H + 1; j++)
                {
                    if (i == 0 && j == 0) map2[i, j] = (T)(object)0;
                    else if (i == 0) map2[i, j] = (T)(object)(j - 1);
                    else if (j == 0) map2[i, j] = (T)(object)(i - 1);
                    else map2[i, j] = map[i - 1, j - 1];
                }
            }

            for (int i = 0; i < W + 1; i++)
            {
                for (int j = 0; j < H + 1; j++)
                {
                    if (mode == 0) Console.Write((dynamic)map2[i, j] % 10);
                    if (mode == 1) Console.Write(map2[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
#endif
        }

        public static void Draw1D(int[] array, int mode = 0)
        {
#if DEBUG
            Console.WriteLine(string.Join(" ", array));
#endif
        }
    }
}


Measured memory_bytes: 27464
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;

int main(){
	long long int N,M,ans=1,w=1000000007;
	cin>>N>>M;
	if(abs(N-M)<2)
	{
		for(int i=N;i>0;i--)
		{
			ans=ans*i%w;
		}
		for(int i=M;i>0;i--)
		{
			ans=ans*i%w;
		}
	}
	else ans=0;
	if(N==M)ans=2*ans%w;
	cout<<ans;
	return 0;
	}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc139/tasks/abc139_b
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define EPS (1e-9)
#define INF (1e9)
#define INFL (1e18)
#define MOD (1000000007)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
// 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; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    cout << n * (n - 1) / 2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define int             long long
#define ld              long double
#define fi              first
#define se              second
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define sq(a)           (a)*(a)
#define fo(i,n)         for(i=0;i<n;i++)
#define fo1(i,n)        for(i=1;i<=n;i++)
#define rep(i,a,b)      for(i=a;i<=b;i++)
#define Fo(i,k,n)       for(i=k;k<=n?i<=n:i>=n;k<=n?i++:i--)
#define all(x)          x.begin(),x.end()
#define rall(x)         x.rbegin(),x.rend()
#define sortall(x)      sort(all(x))
#define sortrall(x)     sort(rall(x))
#define clr(x)          memset(x,0,sizeof(x))
#define tr(it, a)       for(auto it=a.begin();it!=a.end();it++)
#define pii             pair<int,int>
#define mk(arr,n,type)  type *arr=new type[n];
#define vi              vector<int>
#define si              set<int>
#define usi             unordered_set<int>
#define mii             map<int,int>
#define umii            unordered_map<int,int>
#define pqmx            priority_queue<int>
#define pqmn            priority_queue<int,vi,greater<int>>
#define setbits(x)      __builtin_popcountll(x)
#define trailzrobits(x) __builtin_ctzll(x)
#define leadzrobits(x)  __builtin_clzll(x)
#define paritybits(x)   __builtin_parityll(x)
#define gcd             __gcd
#define lcm(x, y)       (x * y)/gcd(x,y)
#define mod             1000000007
#define endl            '\n'
#define PI              3.1415926535897932384626
#define inf             1e18
#define sp(x,y)         fixed<<setprecision(y)<<x
void __print(int32_t x) {cout<<x;}
void __print(int x) {cout<<x;}
void __print(ld x) {cout<<x;}
void __print(double x) {cout<<x;}
void __print(float x) {cout<<x;}
void __print(bool x) {cout<<(x?"true":"false");}
void __print(char x) {cout <<'\''<<x<<'\'';}
void __print(const char *x) {cout <<'\"' <<x<<'\"';}
void __print(const string &x) {cout<<'\"'<<x<<'\"';}
template<typename T,typename V>     void __print(const pair<T,V> &x) {cout<<'{';__print(x.first);cout<<',';__print(x.second);cout<<'}';}
template<typename T>                void __print(const T &x) {int f=0;cout<<'{';for(auto &i:x)cout<<(f++?",":""),__print(i);cout<<"}";}void _print(){cout<<"]\n";}
template <typename T,typename... V> void _print(T t, V... v) {__print(t);if(sizeof...(v))cout<<", ";_print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout<<"["<<#x<<"]=[";_print(x)
#else 
#define dbg(x...)
#endif
int power(int base,int exp) {int res=1;base%=mod;while(exp>0){if(exp&1)res=(res*base)%mod;base=(base*base)%mod;exp=exp>>1;}return res;}
int inv(int x) {return power(x,mod-2)%mod;}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++




const int N=1e6+6,M=N;
int i,j;

void solve() {
    
    int n; cin>>n;
    int cnt=0;
    fo1(i,n){
        int a; cin>>a;
        if((i&1) and (a&1)) cnt++;
    }
    cout<<cnt;
    
    
    
}




int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

Measured memory_bytes: 3648
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<map>
#include<math.h>
#include<string>
#include <cctype>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = s; i < (int)(n); i++)
#define out(x) cout << x << endl
#define INF 1ll<<60;

using namespace std;
using ll = long long;
typedef pair<int, int> P;

int main(){
    int n; cin >> n;
    string s, t; cin >> t >> s;
    rep(i, s.size()+t.size()){
        if(i%2) cout << s[i/2];
        else cout << t[i/2];
    }
    cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
    int temp = 0;
    int ans = 0 ;
    
    string s; ;
    cin >> s ;
    size_t n = s.length() ;
    s[n] = 'D'; 
    for(int i = 0; i < n + 1; i++){
        if(s[i] == 'A' ||s[i] == 'C'||s[i] == 'G' ||s[i] == 'T'){
            temp++;
        }else{
            if(temp > ans){
                ans = temp ;
            }
            temp = 0 ;
        }

    }
    cout << ans <<  endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  int ans = 0;
  for (int i = 1; i < N + 1; ++i) {
    if (i % 2 == 0) continue;
    int count = 0;
    for (int j = 1; j < i + 1; ++j) {
      if (i % j == 0) ++count;
    }
    if (count == 8) ++ans;
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=998244353;
int main(){
  ll n,m;cin>>n>>m;
  vector<ll>x(n);
  vector<ll>y(n);
  set<ll>xx;
  set<ll>yy;
  rep(i,n){
    cin>>x[i]>>y[i];
    xx.insert(x[i]);
    yy.insert(y[i]);
  }
  xx.insert(inf);
  yy.insert(inf);
  xx.insert(-inf);
  yy.insert(-inf);
  ll h=xx.size();
  ll w=yy.size();
  vector<vector<ll> >g(h+2,vector<ll>(w+2));
  ll i=0;
  map<ll,ll>mpx;
  map<ll,ll>mpy;
  for(auto e:xx){
    mpx[e]=i;
    i++;
  }
  i=0;
  for(auto e:yy){
    mpy[e]=i;
    i++;
  }
  rep(i,n){
    g[mpx[x[i]]][mpy[y[i]]]++;
  }
  REP(i,1,h+1){
    REP(j,1,w+1){
      g[i][j]+=g[i][j-1];
    }
  }
  REP(i,1,h+1){
    REP(j,1,w+1){
      g[i][j]+=g[i-1][j];
    }
  }
  //cout<<endl;
  REP(i,1,h+1){
    REP(j,1,w+1){
      //cout<<g[i][j]<<' ';
    }
    //cout<<endl;
  }
  rep(i,m){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll A=mpx[*xx.lower_bound(a)];
    ll B=mpy[*yy.lower_bound(b)];
    ll C=mpx[*xx.upper_bound(c)];
    ll D=mpy[*yy.upper_bound(d)];
    C--;
    D--;
    //cout<<A<<' '<<B<<' '<<C<<' '<<D<<endl;
    cout<<g[C][D]+g[A-1][B-1]-g[A-1][D]-g[C][B-1]<<endl;
  }
}


Measured memory_bytes: 199784
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define SORT(c) sort((c).begin(),(c).end())
#define ANS(ans) cout<<(ans)<<endl;
typedef vector<int> VI;


//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  for (int i = 0; i < (n); ++i)


int main() {
	int x1, x2, y1, y2;
	cin >> x1 >> y1 >> x2 >> y2;

	int vx, vy;
	vx = x2 - x1;
	vy = y2 - y1;

	int x3, y3, x4, y4;

	x3 = x2 - vy;
	y3 = y2 + vx;

	x4 = x3 - vx;
	y4 = y3 - vy;

	cout << x3 << " " << y3 << " " << x4 << " " << y4<<endl;


	return 0;
}

Measured memory_bytes: 256
a=list(map(int,input().split()))
N=a[0]
M=a[1]
posx=[]
posy=[]
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    posx.append(x1)
    posy.append(y1)
students=[10**9]*N
aim=[0,]*N
for i in range(M):
    pointx,pointy=[int(i) for i in input().split()]
    for j in range(N):
        if students[j] > abs(pointx-posx[j]) + abs(pointy-posy[j]):
            students[j] = abs(pointx-posx[j]) + abs(pointy-posy[j])
            aim[j]=i+1
for i in range(N):
    print(str(aim[i]))

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <string>
#include <numeric>
#include <math.h>
#include <set>
#include <map>
#include <fstream>
#include <sstream>
#include <iterator>
#include <complex>
using namespace std;

long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcd(long long a,long long b){return a*b / gcd(a,b) / gcd(a,b);}
int main()
{
	int K,N;
	cin>>K>>N;

	vector<int> A(N);

	for(int i=0; i<N; i++)
	{
		cin>>A[i];
	}
	vector<int> B(N);
	for(int i=0; i<N-1; i++)
	{
		B[i] = A[i+1] - A[i];
	}
	B[N-1] = A[0] + K - A[N-1];

	int result = accumulate(B.begin(),B.end(), -*max_element(B.begin(),B.end()));
	cout<<result<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    int N, temp;
    cin >> N;
    vector <int> res;
    vector <int> srt_res;
    for(int i = 0; i < N; i++){
        cin >> temp;
        res.push_back(temp);
        srt_res.push_back(temp);
    }
    sort(srt_res.rbegin(), srt_res.rend());
    bool t = false;
    for(int i = 0; i < N; i++) {
        t = false;
        for (auto it = srt_res.begin(); it != srt_res.end(); it++) {
            if (*it != res[i] || t){
                cout << *it << "\n";
                break;
            }
            else if (*it ==  res[i])
                t = true;
        }
    }
    return 0;
}


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

using namespace std;

int exclamation(int num) {
    if(num == 1) {
        return 1;
    } 

    return num * exclamation(num-1);
}

int main() {
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    vector<int> town(N);
    double length = 0;
    double sum = 0;
    
    for(int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        town[i] = i;
    }

    do {
        length = 0;

        for(int i = 0; i < N-1; i++) {
            length += sqrt(pow(double(x[town[i]] - x[town[i+1]]), 2.0) + pow(double(y[town[i]] - y[town[i+1]]), 2.0));
        }

        sum += length;

    } while(next_permutation(town.begin(), town.end()));

    sum /= double(exclamation(N));

    cout << fixed << setprecision(10) << sum << endl;
	return 0;
}

Measured memory_bytes: 3740
/*
@author: sharrad99
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	string s;
	cin >> s;

	vector<int> r, g, b;
	for(int i = 0; i < n; i++) {
		if(s[i] == 'R') r.emplace_back(i);
		if(s[i] == 'G') g.emplace_back(i);
		if(s[i] == 'B') b.emplace_back(i);
	}

	int64_t res = 0;
	for(int i = 0; i < n; i++) {
		if(s[i] == 'R') {
			for(int j = i + 1; j < n; j++) {
				if(s[j] == 'R') continue;
				if(s[j] == 'G') {
					int d = (j - i);
					int k = j + d;
					auto p = lower_bound(b.begin(), b.end(), j + 1) - b.begin();
					res += (b.size() - p);
					auto it = lower_bound(b.begin(), b.end(), k);
					if(it != b.end() and *it == k) {
						res--;
					}
				}
				if(s[j] == 'B') {
					int d = (j - i);
					int k = j + d;
					auto p = lower_bound(g.begin(), g.end(), j + 1) - g.begin();
					res += (g.size() - p);
					auto it = lower_bound(g.begin(), g.end(), k);
					if(it != g.end() and *it == k) {
						res--;
					}
				}
			}
		}
		if(s[i] == 'G') {
			for(int j = i + 1; j < n; j++) {
				if(s[j] == 'G') continue;
				if(s[j] == 'R') {
					int d = (j - i);
					int k = j + d;
					auto p = lower_bound(b.begin(), b.end(), j + 1) - b.begin();
					res += (b.size() - p);
					auto it = lower_bound(b.begin(), b.end(), k);
					if(it != b.end() and *it == k) {
						res--;
					}
				}
				if(s[j] == 'B') {
					int d = (j - i);
					int k = j + d;
					auto p = lower_bound(r.begin(), r.end(), j + 1) - r.begin();
					res += (r.size() - p);
					auto it = lower_bound(r.begin(), r.end(), k);
					if(it != r.end() and *it == k) {
						res--;
					}
				}
			}
		}
		if(s[i] == 'B') {
			for(int j = i + 1; j < n; j++) {
				if(s[j] == 'B') continue;
				if(s[j] == 'R') {
					int d = (j - i);
					int k = j + d;
					auto p = lower_bound(g.begin(), g.end(), j + 1) - g.begin();
					res += (g.size() - p);
					auto it = lower_bound(g.begin(), g.end(), k);
					if(it != g.end() and *it == k) {
						res--;
					}
				}
				if(s[j] == 'G') {
					int d = (j - i);
					int k = j + d;
					auto p = lower_bound(r.begin(), r.end(), j + 1) - r.begin();
					res += (r.size() - p);
					auto it = lower_bound(r.begin(), r.end(), k);
					if(it != r.end() and *it == k) {
						res--;
					}
				}
			}
		}
	}

	cout << res << '\n';
}

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

int main()
{
    int k, a, b, c;
    cin >> k >> a >> b;
    c = a;
    for(int i = a; i<=b; i++){
       if(i%k == 0 ){
           c = i;
       }
    }
    if(c%k == 0 ){
        cout << "OK" << endl;
    }else{
        cout << "NG" << endl;
    }
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<algorithm>
using namespace std;
long long int d[1000000];
int main()
{
	long long int n;
	scanf("%ld",&n);
	for(long long int i=1;i<=n;i++)
	scanf("%ld",&d[i]);
	sort(d+1,d+n+1);
	long long int m,p;
	m=n/2+1;
	p=n/2;
	printf("%ld\n",d[m]-d[p]);
	return 0;
}

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

using State = string::const_iterator;

map<string, int> table;
bool unknown;

int molecule(State &itr);
int atom(State &itr);
int number(State &itr);

void next_char(State &itr, char expected){
    if(*itr == expected){
        itr++;
    }else{
        // error
        while(*itr){
            itr++;
        }
    }
}

int molecule(State &itr){
    int w = 0;
    if(isupper(*itr)){
        w = atom(itr);
    }else if(*itr == '('){
        next_char(itr, '(');
        w = molecule(itr);
        next_char(itr, ')');
    }else{
        // error
        cout << "this is not molecule" << endl;
    }
    int num = number(itr);
    w *= num;
    if(*itr && (isupper(*itr) || *itr=='(')){
        w += molecule(itr);
    }
    return w;
}

int atom(State &itr){
    string name = "";
    if(isupper(*itr)){
        name.push_back(*itr);
        itr++;
        while(islower(*itr)){
            name.push_back(*itr);
            itr++;
        }
    }else{
        // error
        cout << "this is not atom" << endl;
    }
    if(table.find(name) != table.end()){
        return table[name];
    }else{
        unknown = true;
        return 0;
    }
}

int number(State &itr){
    int res = 0;
    while(isdigit(*itr)){
        res = res*10 + *itr-'0';
        itr++;
    }
    return max(res, 1);
}

int solve(){
    string s;
    while(cin >> s){
        if(s == "END_OF_FIRST_PART") break;
        int w;
        cin >> w;
        table[s] = w;
    }
    while(cin >> s){
        if(s == "0") break;
        State begin = s.begin();
        int ans = 0;
        unknown = false;
        ans = molecule(begin);
        if(unknown){
            cout << "UNKNOWN" << endl; 
        }else{
            cout << ans << endl;
        }
    }
    return 0;
}

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



Measured memory_bytes: 3188
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Sagor
 */

#include <fstream>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

#define gap                        ' '
#define EPS                        1e-9
#define P_INF                      2e9+17
#define N_INF                     -2e9-17
#define MOD                        1000000007
#define PI                         2*acos(0.0)
#define All(x)                     x.begin(),x.end()
#define Mem(Name, type)            memset(Name, type, sizeof(Name))

template<typename T>
T GCD(T a, T b) { return a ? GCD(b % a, a) : b; }

template<typename T>
T LCM(T a, T b) { return (a * b) / GCD(a, b); }

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (auto ob : v) os << ob << " ";
    return os;
}

template<typename T, typename S>
std::ostream &operator<<(std::ostream &os, const std::map<T, S> &v) {
    for (auto ob : v) os << ob.first << " : " << ob.second << std::endl;
    return os;
}

using ld = double;
using ll = long long int;
using ul = unsigned long long int;
using namespace std;

class AFrog1 {
    int n;
    vector<int> h;
    vector<int> dp;

    int MiniCost(int pos) {
        if (pos == n - 1) return 0;
        if (pos > n - 1) return P_INF;
        if (dp[pos] < P_INF) return dp[pos];

        int oneZump = abs(h[pos] - h[pos + 1]) + MiniCost(pos + 1);
        int twoZump = P_INF;
        if (pos + 2 <= n - 1)
            twoZump = abs(h[pos] - h[pos + 2]) + MiniCost(pos + 2);

        return dp[pos] = min(oneZump, twoZump);
    }

public:
    void solve(std::istream &in, std::ostream &out) {
        in >> n;
        h.resize(n);
        dp.resize(n);
        for (int i = 0; i < n; ++i) {
            in >> h[i];
            dp[i] = P_INF;
        }
        dp[n - 1] = 0;
        out << MiniCost(0) << endl;
    }
};


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    AFrog1 solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 10296
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <functional>
#include <chrono>
#include <cstring>
#include <limits.h>

using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<lint> vl;
typedef pair<lint,lint> pll;

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

    char c; cin>>c;

    if (c - 'A' <= 25) cout<<'A';
    else cout<<'a';



}


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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

LL t,pw25[2000010],pw26[2000010],fac[2000010],ans=0;
string s;

LL fastpow(LL x,LL a)
{
	LL res=x,ret=1;
	while(a>0)
	{
		if((a&1)==1) ret=ret*res%MOD;
		a>>=1;
		res=res*res%MOD;
	}
	return ret;
}
 
LL C(LL n,LL m)
{
	return fac[n]*fastpow(fac[m],MOD-2)%MOD*fastpow(fac[n-m],MOD-2)%MOD;
}

int main()
{
	pw25[0]=pw26[0]=fac[0]=1;
	repn(i,2000005)
	{
		pw25[i]=pw25[i-1]*25LL%MOD;
		pw26[i]=pw26[i-1]*26LL%MOD;
		fac[i]=fac[i-1]*(LL)i%MOD;
	}
	cin>>t>>s;
	rep(i,t+1) ans=(ans+pw26[i]*C(t-i+s.size()-1,s.size()-1)%MOD*pw25[t-i])%MOD;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 52172
n,x = map(int, raw_input().split())
lis = sorted(map(int, raw_input().split()))
def gcd(a, b):
    if a == 0:
        return b
    return gcd(b%a,a)
if n == 1:
    val = abs(lis[0]-x)
    print val
    exit()
val = 0
#print lis
for i in xrange(n):
    lis[i] -= x
    val = gcd(abs(lis[i]), val)
print val

Measured memory_bytes: 11320
#include<iostream>
#include<cstdio>
using namespace std;
int a,b,c;
int main()
{
    while(~scanf("%d%d",&a,&b))
    {
        c = a+b;
        if(a%3 == 0||b%3 == 0||c%3 == 0)
        {
            printf("Possible\n");
            continue;
        }
        printf("Impossible\n");
    }
    return 0;
}


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

int main()
{
    ll n,w;
    cin>>n>>w;
    ll a[n][2];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i][0]>>a[i][1]; // weight value
    }
    
    ll dp[n+1][w+1];
    
    for(ll i=0;i<=n;i++)
        dp[i][0] = 0;
    
    for(ll i=0;i<=w;i++)
        dp[0][i] = 0;
    
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=w;j++)
        {
            if(j < a[i-1][0])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j-a[i-1][0]] + a[i-1][1], dp[i-1][j]);
        }
    }
    cout<<dp[n][w]<<endl;

}

Measured memory_bytes: 79104