akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

class Segtree:
    def __init__(self, A, ide_ele, segfunc):
        self.n = len(A)
        self.size = 2 ** (self.n - 1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.data = [ide_ele] * self.size + A + [ide_ele] * (self.size - self.n)
        for i in range(self.size - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def update(self, k, x):
        k += self.size
        self.data[k] = max(x, self.data[k])
        while k:
            k = k >> 1
            self.data[k] = self.segfunc(self.data[2 * k], self.data[2 * k + 1])

    def query(self, l, r):
        L, R = l + self.size, r + self.size
        s = self.ide_ele
        while L < R:
            if R & 1:
                R -= 1
                s = self.segfunc(s, self.data[R])
            if L & 1:
                s = self.segfunc(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

n,k=LI()
seg=Segtree([0]*300010, -INF, max)
for _ in range(n):
    v=I()
    m=seg.query(max(v-k,0),min(300001,v+k+1))+1
    seg.update(v,m)

print(seg.query(0,300002))



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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int M;
int cnt[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		if(x==1 || x==N) cnt[y]++;
		if(y==1 || y==N) cnt[x]++;
	}
	FOR(i,N+1) if(cnt[i]==2) return _P("POSSIBLE\n");
	_P("IMPOSSIBLE\n");
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  string S;
  cin >> S;

  int N = S.size();
  rep(i,N){
    if(S[i] != S[N-1-i]){
      cout << "No" << endl;
      return 0;
    }
  }

  string T1 = S.substr(0,(N-1)/2);
  string T2 = S.substr((N+3)/2-1);
  //cerr << S << " " << T1 << " " << T2 << endl;

  rep(i,T1.size()){
    if(T1[i] != T1[T1.size()-1-i]){
      cout << "No" << endl;
      return 0;
    }
  }
  rep(i,T2.size()){
    if(T2[i] != T2[T2.size()-1-i]){
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  
  return 0;
}



Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int[] a = new int[n]; for(int i=0; i<n; i++) a[i] = Integer.parseInt(st.nextToken());
        double ans = 0;
        for(int i=0; i<n; i++) ans += 1.0/a[i];
        ans = 1.0/ans;
        out.println(ans);

        // int n = Integer.parseInt(st.nextToken());

        out.close(); System.exit(0);
    }
}


Measured memory_bytes: 22228
#include<bits/stdc++.h>
using namespace std;
#define int long
using pi=pair<int,int>;
signed main(){
    string s,t;
    cin>>s>>t;
    for(int i=0;i<s.size();++i)if(s[i]!=t[i])
            return cout << "No", 0;
    cout << "Yes";
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

  vector<int64_t> dpl(K + 1);
  int nonzero = 0;

  rep(i, N.size() + 1) {
    int d = N[i - 1] - '0';
    rrep(j, K + 1) {
      if (i == 0) {
        dpl[j] = 0;
      } else {
        dpl[j] = dpl[j];
        dpl[j] += (j > 0) ? 9 * dpl[j - 1] : 0;
        dpl[j] += (j == nonzero && d > 0) ? 1 : 0;
        dpl[j] += (j - 1 == nonzero && d > 0) ? d - 1 : 0;
      }
      cerr << dpl[j] << " ";
    }
    cerr << endl;
    if (d > 0) {
      nonzero++;
    }
  }

  cout << (nonzero == K ? 1 : 0) + dpl[K] << endl;

  return 0;
}

Measured memory_bytes: 256
N,K = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
B = []

for p_item in p:
  B.append(float((p_item+1)/2))
  
Max = sum(B[:K])
tmp = sum(B[:K])

for i in range(len(B)-K):
    tmp = tmp - B[i] + B[i+K]
    if Max < tmp:
      Max = tmp

print(Max)

Measured memory_bytes: 25188
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
string S,T,U;
ll N,K;
ll p[200001];
ll ans;




int main(){
    cin >> N>>K;
    for (ll i=0;i<N;i++){
        ll a;
        cin >> a;
        p[i] = 1+a;
    }
    ll start=0;
    for(ll i=0;i<K;i++){
        start += p[i];
    }
    ll next;
    ans = start;
    for (ll i=K;i<N;i++){
        next = start - p[i-K] + p[i];
        if(next > ans){
            ans = next;
        }
        start = next;
    }
    if(ans%2 == 0){
        cout << ans/2 << endl;
    }else{
        cout << ans/2 << ".5" << endl;
    }

    
}




Measured memory_bytes: 1792
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;

ll pow(ll x,ll n){
    if(n==0) return 1;
    else if(n%2) return x*pow(x,n-1);
    return pow(x*x,n/2);
}

ll X;

int main(){
    cin>>X;

    ll A=0,B=0;
    for(ll i=-500;i<=500;i++){
        for(ll j=-500;j<=500;j++){
            if(pow(i,5)-pow(j,5)==X){
                A=i;
                B=j;
                break;
            }
        }
    }

    cout<<A<<' '<<B<<endl;
}

Measured memory_bytes: 4044
#include<stdio.h>
int main(void) {
    int r,d,x[11],i;
    scanf("%d%d%d",&r,&d,&x[0]);
    for(i = 1; i <= 10; i++) {
        x[i] = x[i-1]*r-d;
        printf("%d\n", x[i]);
    }
    return 0;
}

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

class BitComb {
 private:
  ll _digits;
  ll _base;
  ll _data[512];
  ll _finished;
  ll _i;

 public:
  BitComb(ll digits, ll base) {
    _digits = digits;
    _base = base;
    _finished = false;
    _i = 0;
    fill_n(_data, 512, 0);
  }

  void next() {
    if (_finished) {
      return;
    }
    for (ll i = 0; i < _digits; i++) {
      if (_data[i] + 1 < _base) {
        _data[i] += 1;
        break;
      } else {
        _data[i] = 0;

        if (i == _digits - 1) {
          _finished = true;
          break;
        }
      }
    }
  }

  ll* data() { return _data; }

  void print() {
    for (ll i = _digits - 1; i >= 0; i--) {
      cout << _data[i];
    }
    cout << endl;
  }

  bool finished() { return _finished; }
};

int main() {
  ll H, W, K;
  scanf("%lld %lld %lld", &H, &W, &K);

  ll total = 0;
  vector<string> lines;
  for (ll i = 0; i < H; i++) {
    string line;
    cin >> line;

    lines.emplace_back(line);

    for (ll i = 0; i < W; i++) {
      if (line[i] == '#') {
        total++;
      }
    }
  }

  auto bc_h = BitComb(H, 2);

  ll ans = 0;

  while (!bc_h.finished()) {
    auto bc_w = BitComb(W, 2);
    while (!bc_w.finished()) {
      ll black_count = 0;
      for (ll y = 0; y < H; y++) {
        for (ll x = 0; x < W; x++) {
          if (lines[y][x] == '#' && (bc_h.data()[y] || bc_w.data()[x])) {
            black_count += 1;
          }
        }
      }
      if (total - black_count == K) {
        ans++;
      }

      bc_w.next();
    }
    bc_h.next();
  }
  cout << ans << endl;
}


Measured memory_bytes: 3676
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    m = I()
    d,c = 0,0
    for i in range(m):
        a,b = LI()
        d += a*b
        c += b
    print(c-1+(d-1)//9)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 41564
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

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

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

LL add(LL a,LL b){
  return (a+b)%mod;
}

LL sub(LL a,LL b){
  return (a+mod-b)%mod;
}

LL mul(LL a,LL b){
  return ((a % mod) * (b % mod)) % mod;
}

LL power(LL x,LL y){//繰り返し二乗法 単品利用可
  if(y==0)return 1;
  else if(y==1)return x%mod;
  else if(y%2==0){
    LL tmp=power(x, y/2) % mod;
    return tmp*tmp%mod;
  }else {
    LL tmp=power(x, y/2) % mod;
    return ((tmp*tmp)%mod)*x%mod;
  }
}

LL dvs(LL a,LL b){
  return mul(a,power(b,mod-2));
}


int invfact[200005];
int fact[200005];

LL factset(int a){//aまでの階乗%mod表を作成
  fact[0]=1;
  FORQ(i,1,a){
    fact[i]=mul(fact[i-1],i);
  }
}

LL cmbset(int a){//1~aまでの階乗と階乗数の逆元のmod(mod)を用意 O(a)
  factset(a);
  invfact[a]=power(fact[a],mod-2);
  invfact[0]=1;
  FORD(i,a,1){
    invfact[i]=mul(invfact[i+1],i+1);
  }

}

LL cmb(int n,int r){//nCr%mod  (cmbset後に使用)
  if(n<r||r<0||n<0)return 0;
  return mul(fact[n],mul(invfact[r],invfact[n-r]));
}

LL prm(int n,int r){//nPr%mod
    return mul(cmb(n,r),fact[n]);
}

LL homo(int n,int r){//nHr%mod
  return cmb(n+r-1,r);
}



int main(){
	LL h,w,a,b;
	LL ans=0;
	cin>>h>>w>>a>>b;
	cmbset(200000);
	FORQ(i,1,h-a){
		LL t=cmb((int)i-1+b-1,(int)i-1);
		LL p=cmb(h-i+w-b-1,h-i);
		ans=add(mul(t,p),ans);
	}
	cout<<ans;

    return 0;
}


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


int main(void) {
    int r;
    cin>>r;
    cout<<3*r*r<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef std::pair<int, int> ipair;
#define int long long
#define pb push_back
#define ff first
#define INF INT_MAX
#define ss second
#define fr(i, j, a) for (int i = j; i < a; i++)
#define cnt_ones(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define sz size()
#define endl "\n"
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<ipair>
#define mod 1000000007
#define IOS                                                                    \
  std::ios::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);
void init() {
  int n, k;
  cin >> n >> k;
  vi h(n);
  for (int &i : h)
    cin >> i;
  sort(all(h));
  int ans = INT_MAX;
  for (int i = 0; i < n; i++)
    if (i + k-1 < n)
      ans = min(ans, h[i + k-1] - h[i]);
  cout << ans << endl;
}
int32_t main() {
  IOS;
  init();
  return 0;
}


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

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

int N;
vector<ll> A, ans;
map<int, int> mp;

void solve(){
    rep(i, N){
        mp[A[i]]++;
    }

    for(auto itr=mp.begin(); itr!=mp.end(); ++itr){
        if(itr->second >= 4) ans.push_back(itr->first);
        if(itr->second >= 2) ans.push_back(itr->first);
    }

    if(ans.size() < 2){
        cout << 0 << endl;
    } else {
        sort(ans.begin(), ans.end());
        reverse(ans.begin(), ans.end());

        cout << ans[0] * ans[1] << endl;
    }
}

int main(){
    cin >> N;

    A.resize(N);

    rep(i, N) cin >> A[i];

    solve();
}


Measured memory_bytes: 5760
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 100005;

int main() {
#ifdef suiyuan2009
  freopen("in.cpp","r",stdin);
#endif // suiyuan2009
  int n;
  cin>>n;
  unordered_map<int,int>mp;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    mp[x]++;
    mp[x+1]++;
    mp[x-1]++;
  }
  int ret=1;
  for(auto tt:mp){
    ret=max(ret,tt.second);
  }
  cout<<ret<<endl;
  return 0;
}



Measured memory_bytes: 4260
#include <iostream>
 using namespace std ;
 int main()
{
 int a,b, c, d,e;
 cin>>a;
cin>>b;
 c=(a*2-1);
 d=(b*2-1);
 e=(a+b);
 if (a > b)
 {
   cout<<c<<endl;
 }
 if  (a < b)
 {
   cout<<d<<endl;
 }
  if (a == b)
{
  cout<<e<<endl;
}
return 0;
}


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

int main(){
  long long H,W;
  cin >> H >> W;
  if(H==1 || W==1){
    cout << 1 << endl;
  }
  else{
    cout << (H*W+1)/2 << endl;
  }
}
    
  

Measured memory_bytes: 3564
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;


ll calc(ll N, ll M){
    if(M>=2*N) return N + (M-2*N)/4;
    return M/2;
}

int main() {
    ll N, M; cin >> N >> M;
    cout << calc(N, M) << endl;
}


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

int main() {
  int a;
  int b;
  int c;
  int d;
  int r;
  int l;
  
  cin >> a >> b >> c >> d;
  
  l = a + b;
  r = c + d;
  
  if (r > l) {
    cout << "Right" << endl;
  }
  else if(r < l) {
    cout << "Left" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>

using namespace std;

int main(){
  int n;
  cin>> n;
  int d,u,s,dp[400];
  memset(dp,-1,sizeof(dp));
  dp[0]=0;
  for(int i=0;i<n;i++){
    cin>>d>>u>>s;
    for(int j=0;j<400;j++)
      for(int k=d;k<=u;k++)
	if(j+k<400 && dp[j]!=-1) dp[j+k] = max(dp[j+k],dp[j]+s);
  }
  
  int q,flg=0,m[400];
  cin>> q;
  for(int i=0;i<q;i++){
    cin >> m[i];
    if(dp[m[i]] == -1) flg= 1;
  }

  if(flg) cout << -1<<endl;
  else 
    for(int i=0;i<q;i++) cout << dp[m[i]]<<endl;
  return 0;
}

Measured memory_bytes: 1164
// by gantheory™
#include <bits/stdc++.h>

using namespace std;

string s;

int main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.setf(ios::fixed);cout.precision(20);
  cin >> s;
  string tmp = "FESTIVAL";
  cout << s.substr( 0, s.size() - tmp.size() ) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string.h>
#define rep(i, n) for(int i = 0; i<(n); i++)
using namespace std;
typedef long long ll;
static const int MAX = 200000; 
//pi = 3.14159265358979323846

int main() {

    int n;
    cin >> n;
    cout << n * n * n << endl;

}




Measured memory_bytes: 256
//・途中のS(S1, S2)について{処理したクエリの個数, 今見てる区間に含まれる1の個数}が同じなら, S2はないものとしてよい。
//・今見てる区間より左側を「何パターン作れるか？」が重要。
//・クエリを変形すると → l_i+1 = l_i + 1, r_i+1 ≧ r_iを満たすクエリにできる。
//あとは、0を追い出すか？1を追い出すか？を適当に試すだけで解ける。(DPで適当に状態をまとめるだけ)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;

const int mod = 1000000007;
int n, m;
string s;
int rui[3001];
vector<int> r;
int dp[3001][3001];		//dp[処理したクエリ数][今見てる区間よりも左側にある1の個数] = 今見てる区間の左側が何パターンあるか？

vector<int> input() {
	int l[3000], r[3000];
	int maxR[3001] = {0};
	
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++) {
		cin >> l[i] >> r[i];
		maxR[l[i]] = max(maxR[l[i]], r[i]);
	}
	for (int i = 1; i <= n; i++) {
		maxR[i] = max(maxR[i - 1], max(i, maxR[i]));
	}
	
	vector<int> ret;	//0-indexed
	for (int i = 1; i <= n; i++) {
		ret.push_back(maxR[i] - 1);
	}
	return ret;
}

signed main() {
	r = input();
	for (int i = 1; i <= n; i++) rui[i] = rui[i - 1] + (s[i - 1] - '0');

	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			int iti  = rui[r[i] + 1] - j;
			int zero = r[i] + 1 - i - iti;
			
			if (iti > 0) {
				dp[i + 1][j + 1] += dp[i][j];
				dp[i + 1][j + 1] %= mod;
			}
			if (zero > 0) {
				dp[i + 1][j] += dp[i][j];
				dp[i + 1][j] %= mod;
			}
		}
	}
	cout << dp[n][rui[n]] << endl;
	return 0;
}

Measured memory_bytes: 69248
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
ans=0
c=0
for i in range(n):
  z=l[i][1]
  if c+z<=m:
    ans+=l[i][0]*z
    c+=z
  else:
    ans+=l[i][0]*(m-c)
    break
print(ans)

Measured memory_bytes: 27756
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int ctoi(char c) {return c-'0';}// char to int
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}//MAX
int lcm(ll a,ll b){return a*b/gcd(a,b);}//MIN
 
int  main(){
vector<bool>che(4,false);
string s;
cin >> s;
for(int i=0;i<s.size();i++){
    if(s.at(i)=='N')che.at(0)=true;
    if(s.at(i)=='E')che.at(1)=true;
    if(s.at(i)=='S')che.at(2)=true;
    if(s.at(i)=='W')che.at(3)=true;
}
if(che.at(0)&&che.at(1)&&che.at(2)&&che.at(3))cout <<"Yes"<<endl;
else if(che.at(0)&&!che.at(1)&&che.at(2)&&!che.at(3))cout <<"Yes"<<endl;
else if(!che.at(0)&&che.at(1)&&!che.at(2)&&che.at(3))cout <<"Yes"<<endl;
else{
    cout <<"No"<<endl;
}
}
 


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define pb push_back
#define ft first
#define sd second
#define mp make_pair
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

int main(){
  int a[3];
  cin>>a[0]>>a[1]>>a[2];
  sort(a,a+3);
  if(a[0]==a[1]&&a[1]==a[2]) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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

int main() {
  int n;
  cin >> n;
  
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  
  int ans = 0;
  for(int i=0; i<n; i+=2) if(a[i]%2==1) ans++;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3520
#include <bits/stdc++.h>
  
using namespace std;
  
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
  
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
  
const int inf = int(1e9);
const int mod = inf + 7;
const int N = 1e6 + 555; // TL MB
const double PI = acos(-1.0);
 
void mul(ll &x, ll y){
	x *= y;
	if(x >= mod) x %= mod;
}
 
void add(ll &x, ll y){
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
ll bp(ll a, ll n){
	ll r = 1;
	while(n){
		if(n & 1) mul(r, a);
		mul(a, a);
		n >>= 1;
	}
	return r;
}

void solve()
{
	int n;
	cin >> n;
	ll t, a;
	ll id = 1, mn = 1e18;
	cin >> t >> a;
	t *= 1000;
	a *= 1000;
	for(int i = 0; i < n; ++i){
		ll h;
		cin >> h;
		ll cur = t - h * 6;
		if(abs(a - cur) < mn){
			mn = abs(a - cur);
			id = i + 1;
		}
	}
	cout << id;
}


 
 
int main()
{
    Red;
  	// int T; cin >> T; while(T--)
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i <= n; i++)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
using namespace std;
ll mod = 1e9 + 7;

int main()
{
	int a, b;
	cin >> a >> b;
	if (a>9 || b>9)
	{
		co(-1);
	}
	else
	{
		co(a * b);
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;

/*--- Macro ---*/
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep1(i, n) for(int i=1; i<(int)n; i++)
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

/*---  Type ---*/
typedef long long ll;

/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;

// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

// Util
int max(int a, int b, int c) {return max(a, max(b, c));}
int min(int a, int b, int c) {return min(a, min(b, c));}
ll max(ll x, ll y) {return x > y ? x : y;}
ll min(ll x, ll y) {return x < y ? x : y;}
ll max(ll a, ll b, ll c) {return max(a, max(b, c));}
ll min(ll a, ll b, ll c) {return min(a, min(b, c));}

// -------------------------------------------------------------------------------------



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

  if(a+b > c+d) cout << "Left" << endl;
  else if(a+b < c+d) cout << "Right" << endl;
  else cout << "Balanced" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MOD	1000000007
#define int	long long
#define pii pair<int,int> 
#define vi vector<int>
using namespace std;

int32_t main(){
	int n, k;
	cin >> n >> k;
	int a[n];
	for(int i = 0; i < n; i++)
		cin >> a[i];
	const int INF = 1e9 + 10;
	vector<int> dp(n,INF);
	dp[0] = 0;
	for(int i = 1; i < n; i++){
		for(int j = i-1; j >= max(0LL,i-k); j--){
			dp[i] = min(dp[i],dp[j] + abs(a[i]-a[j]));
		}
	}
	cout << dp[n-1] << endl;

	return 0;
}



Measured memory_bytes: 1792
#include <cstdio>
#include <cstdint>

intmax_t ban(int n, intmax_t x) {
  fprintf(stderr, "%d %jd\n", n, x);
  if (!n) return x;
  if (!n || !x) return 0;
  intmax_t p = (2LL<<n)-1;
  intmax_t m = (4LL<<n)-3;
  fprintf(stderr, "%jd %jd\n", p, m);
  if (x >= m) return p;
  intmax_t res = 0;
  if (x > m/2) {
    res += ban(n-1, m/2-1);
    x -= m/2+1;
    res += 1;
    res += ban(n-1, x);
  } else {
    res += ban(n-1, x-1);
  }
  return res;
}

int main() {
  int n;
  intmax_t x;
  scanf("%d %jd", &n, &x);

  printf("%jd", ban(n, x));
}

Measured memory_bytes: 128
#include <algorithm>
#include <cstdio>
using namespace std;
int f[20001];
int n, m;
int main() {
    scanf("%d %d", &n, &m);
    f[0] = 0;
    for (int i = 1; i <= n + 1; i ++)
        f[i] = 1e9;
    while (m --) {
        int x, y;
        scanf("%d %d", &x, &y);
        do{
            for (int i = n; i >= 0; i --)
                f[i] = min(min(f[i], f[i + 1]), f[max(i - x, 0)] + y);
            x += x, y += y;
        }while (x / 2 <= n);
    }
    printf("%lld\n", f[n]);
    return 0;
}

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

int n;

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

    cin >> n;
    vector<int> w(n+3,0);
    for(int i=1;i<=n;i++)cin >> w[i];
    vector<int> suf(n+3,0);
    for(int i=n;i>=1;i--)suf[i] = w[i] + suf[i+1];
    int ans = 2e9, sum = 0;
    for(int i=1;i<=n;i++){
        sum += w[i];
        ans = min(ans, abs(sum - suf[i+1]));
    }
    cout << ans << '\n';


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

ll com(int n,int k){
    ll res = 1;
    for(int i=0;i<k;i++){
        res *= n-i;
        res /= i+1;
    }
    return res;
}

int main(){
    int n,a,b;
    cin >> n >> a >> b;
    vector<ll> v(n);
    rep(i,n) cin >> v[i];
    sort(v.rbegin(),v.rend());
    ll res = 0;
    rep(i,a) res += v[i];
    cout << setprecision(20) << (res/(double)a) << endl;
    ll c=0,cc=0;
    rep(i,n){
        cc += (v[a-1]==v[i]);
        if(i<a) c += (v[a-1]==v[i]);
    }
    ll now = com(cc,c);
    if(v[0]!=v[a-1]){
        cout << now << endl;
        return 0;
    }
    ll ans = 0;
    for(int i=a;i<=min(cc,(ll)b);i++){
        ans += com(cc,i);
    }
    cout << ans << endl;
    return 0;
}

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

const long long md = 1e9+7;
int main(){
  long long N, M; cin >> N >> M;
  set<int> a;
  for (int i=0; i<M; i++){
    int A;
    cin >> A;
    a.insert(A);
  }
  vector<long long> dp(N+1,0);
  dp[0] = 1;
  for (int i=1; i<=N; i++){
    if (a.find(i)!=a.end()){
      continue;
    }
    else {
      if (i>1) dp[i] = dp[i-1] + dp[i-2];
      else dp[i] = dp[i-1];
    }
    dp[i] %= md;
  }
  cout << dp[N] << endl;
}


Measured memory_bytes: 5760
import java.io.*;
import java.util.*;
//import javafx.util.Pair;
import static java.lang.System.*;
import static java.lang.Math.*;

public class Main
{
	public static void main(String []args)throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		//String []s=br.readLine().split(" ");
		//int N = Integer.parseInt(s[0]);
		//int M = Integer.parseInt(s[1]);
		
		int arr[]=new int[2];	
		
		char ch[]=br.readLine().toCharArray();
		
		for(int i=0;i<ch.length;i++)
		{
			if(ch[i]=='A')
				arr[0]++;
			else
				arr[1]++;
		}	

		if(arr[0]>0 && arr[1]>0)
			out.println("Yes");
		else
			out.println("No");
		
		
	}
	
	
}




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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);

    ll N;
    cin >> N;

    ll jpy = 0;
    double bit = 0.0;
    REP(i, N){
        double x;
        string u;
        cin >> x >> u;

        if(u == "JPY"){
            jpy += x;
        }
        else{
            bit += x;
        }
    }
    cout << jpy + 380000.0*bit << endl;
    return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

#define INF INT_MAX/3
#define REP(i,n) for(int i=0;i<n;i++)

int main(){
	int N;
	map<int,int> arr;
	cin>>N;
	REP(i,N){
		int a;
		cin>>a;
		arr[a]++;
		arr[a+1]++;
		arr[a-1]++;
	}
	int max_n = 0;
	for(auto& s : arr){
		if(max_n < s.second){
			max_n = s.second;
		}
	}
	
	cout<<max_n<<endl;

	return 0;
}


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

int cmpnum(const void * n1, const void * n2) {
	if (*(long *)n1 > *(long *)n2)
	{
		return -1;
	}
	else if (*(long *)n1 < *(long *)n2)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int main(void) {

  long n;
  scanf("%ld", &n);
  long a[n];
  for (long i = 0; i < n; i++) {
    scanf("%ld", &a[i]);
  }
  qsort(a, n, sizeof(long), cmpnum);
  long score = a[0];
  long cur = 0;
  for (long i = 2; i < n; i++) {
    if (i%2 == 0) {
      cur++;
    }
    score += a[cur];
  }
  printf("%ld\n", score);

  return 0;
}

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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


using Int = __int128_t;
Int abs128(Int val){return val<0?-val:val;}

ostream &operator<<(ostream &os,Int val){
  if(ostream::sentry(os)){
    __uint128_t tmp=abs128(val);
    char buf[64];
    char *d=end(buf);
    do{
      --d;
      *d=char(tmp%10+'0');
      tmp/=10;
    }while(tmp);
    if(val<0) *--d='-';
    Int len=end(buf)-d;
    if(os.rdbuf()->sputn(d,len)!=len){
      os.setstate(ios_base::badbit);
    }
  }
  return os;
}

istream &operator>>(istream &is,Int &val){
  string s;
  is>>s;
  val=0;
  for(Int i=0;i<(Int)s.size();i++)
    if(isdigit(s[i])) val=val*10+s[i]-'0';
  if(s[0]=='-') val*=-1;
  return is;
}


//INSERT ABOVE HERE
signed main(){
  Int n,a;
  cin>>n>>a;
  vector<Int> x(n);
  for(Int i=0;i<n;i++) cin>>x[i];

  Int sum=0;
  for(Int i=0;i<n;i++) sum+=x[i]*5;

  vector<Int> s(n+1,0);
  for(Int i=0;i<n;i++) s[i+1]=s[i]+x[i];
  
  Int ans=sum+n*a;
  for(Int i=1;i<n;i++){
    Int res=sum+i*a,cnt=-2;
    for(Int j=n-i;;j-=i,cnt+=2){
      Int k=(j<0?0:j);
      if(cnt>0) res+=(s[j+i]-s[k])*cnt;
      if(k==0) break;
    }
    chmin(ans,res);
  }
  cout<<ans+n*a<<endl;
  return 0;
}


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

using namespace std;

const int MaxN = (int)1e3 + 10;
const int MOD = (int)1e9 + 7;
const int INF = 1e9;

int main() {
//	freopen("input.txt", "r", stdin);
//	ios::sync_with_stdio(false); cin.tie(NULL);
	int a, b, c;
	long long k;
	cin >> a >> b >> c >> k;
	if (k % 2 == 0) {
		cout << a - b << "\n";
	} else {
		cout << b - a << "\n";
	}
	return 0;
}


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

using namespace std;

int n;
int k;
int main() {
  cin >> n >> k;
  int ans = 0;
  for(int i = 0; i < n; i++) {
    int x;
    cin >> x;
    ans += min(x,k-x);
  }

  cout << ans * 2<< endl;
}
    


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main()
{
	ll N, A, B; cin >> N >> A >> B;
	ll sum = 0;
	repe(i, 0, N) {
		int t = i;
		int s = 0;
		while (t != 0) {
			s += t % 10;
			t /= 10;
		}

		if (s >= A && s <= B)
		{
			sum += i;
		}
	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
int n,a,b,i,x=0,y=0;
while(1){
	x=0;
	y=0;
scanf("%d",&n);
if(n==0){
break;}
for(i=0;i<n;i++)
{
scanf("%d %d",&a,&b);
if(a>b)
{
x=x+a+b;
}
else if(a<b)
{
y=y+a+b;
}
else if(a==b)
{
x=x+a;
y=y+b;
}}
printf("%d %d\n",x,y);
}
return 0;
}

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

int main() {
    using namespace std;

    int H, W;
    cin >> H >> W;

    char box[100][100] = {'.'};

    for (int i=0; i<H; i++) {
        string s;
        cin >> s;
        for (int j=0; j<W; j++) {
            box[i+1][j+1] = s[j];
        }
    }

    for (int i=1; i<H+1; i++) {
        for (int j=1; j<W+1; j++) {
            if (box[i][j] == '#') {
                cout << '#';
                continue;
            }

            int count = 0;
            if (box[i-1][j-1] == '#')    count++;
            if (box[i][j-1] == '#')    count++;
            if (box[i+1][j-1] == '#')    count++;
            if (box[i-1][j] == '#')    count++;
            if (box[i+1][j] == '#')    count++;
            if (box[i-1][j+1] == '#')    count++;
            if (box[i][j+1] == '#')    count++;
            if (box[i+1][j+1] == '#')    count++;

//            box[i][j] = count;
            cout << count;
        }

        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 256
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type Abbreviation ---------- */
using ll = long long;

/* ---------- Constants ---------- */
const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* ---------- Short Functions ---------- */
template <typename T>
T gcd(T a, T b) {
    if (a > b) return gcd(b, a);
    return a == 0 ? b : gcd(b % a, a);
}

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b /* % MOD */;
    if (n % 2 == 0) {
        return mypow(b * b /* % MOD */, n / 2);
    } else {
        return mypow(b, n - 1) * b /* % MOD */;
    }
}

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

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

    vector<pair<ll, ll>> pairs;
    for (int i = 0; i < N; i++) {
        ll x;
        cin >> x;
        pairs.push_back(make_pair(x, i));
    }

    sort(pairs.begin(), pairs.end());

    ll rets[N];
    ll centerIdx = (N - 2) / 2;

    for (int i = 0; i < N; i++) {
        if (centerIdx >= i) {
            rets[pairs[i].second] = pairs[centerIdx + 1].first;
        } else {
            rets[pairs[i].second] = pairs[centerIdx].first;
        }
    }

    for (int i = 0; i < N; i++) {
        cout << rets[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 7660
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9+5;
int main()
{
    int n,k;
    scanf("%d %d", &n, &k);
    vector<int> h(n);
    vector<int> dp(n, INF);
    for(int& x : h)
        scanf("%d", &x);
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j = i+1; j <= i+k; j++)
        {
            if(j<n)
                dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]));
        }
    }
    cout << dp[n-1];
    //while(1);
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;

#define sz(x) (int)(x.size())
#define rep(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

////////////////////////

ll const INF = 1e18;

pll get(int w, int h){
	pll ret = mp((w+1)/2 * 1LL * h, w/2 * 1LL * h);
	return ret;
}

ll calc(ll s1, int w, int h){
	ll ret = INF;
	vector<ll> a;
	pll v1 = get(w, h);
	pll v2 = get(h, w);
	a.pb(s1);
	a.pb(v1.first);
	a.pb(v1.second);
	sort(a.begin(), a.end());
	ret = a.back() - a[0];

	a.clear();
	a.pb(s1);
	a.pb(v2.first);
	a.pb(v2.second);
	sort(a.begin(), a.end());
	ret = min(ret, a.back() - a[0]);
	return ret;
}

void solve(){
	ll ans = INF;
	int n, m;
	cin >> n >> m;
	rep(i, 1, n){
		ans = min(ans, calc(i * 1LL * m, n - i, m));
	}
	swap(n, m);
	rep(i, 1, n){
		ans = min(ans, calc(i * 1LL * m, n - i, m));
	}
	

	cout << ans << endl;
}

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

	solve();

	return 0;
}

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

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


int main(){
    
    for(ll N, M; cin >> N >> M, N;){
        vector<ll>mx(N, 0);
        vector<ll>mn(N, 0);
        for(ll i = 0; i < M; i++){
            ll s, k;
            cin >> s >> k;
            for(ll j = 0; j < k; j++){
                ll c;
                cin >> c;
                c--;
                if(k == 1)mn[c] += s;
                mx[c] += s;
            }
        }
        ll ans = 0;
        P x(-1, -1), y(-2, -2);
        for(ll i = 0; i < N; i++){
            if(mx[i] >= x.first){
                swap(x, y);
                x.first = mx[i];
                x.second = i;
            }
            else if(mx[i] >= y.first){
                y.first = mx[i];
                y.second = i;
            }
        }
        for(ll i = 0; i < N; i++){
            if(i == x.second)continue;
            ans = max(ans, mx[x.second] - mn[i]);
        }
        for(ll i = 0; i < N; i++){
            if(i == y.second)continue;
            ans = max(ans, mx[y.second] - mn[i]);
        }
        cout << ans + 1 << endl;
    }
    
    return 0;    
}


Measured memory_bytes: 3236
n,k=map(int,input().split())
a=[]
en=0
for s in range(1,n+1):
 m=0
 en=0
 while en==0:
  if (2**m)*s<k:
    m+=1
  else:
    a.append(1/2**m)
    en+=1

print(sum(a)/n)


Measured memory_bytes: 6296
'use strict'
const Main = (arg) => {
  let input = arg.trim().split('\n');
  let N = input[0].split(' ').map(Number)[0];
  // let Arr1 = input[1].split(' ').map(Number);
  let Res = [];

  // 連想配列(Dictionary)に格納
  for (let i = 1; i <= N; i++) {
    Res[i - 1] = {
      souceOrder: i,
      city: input[i].split(' ')[0],
      score: parseInt(input[i].split(' ')[1]),
      printOrder: 1
    }
  }

  // console.log({ N, Res });
  // console.log(Res[0]);

  // city昇順 score降順 の順に並べ替え
  Res.sort((a, b) => {
    if (a.city < b.city) return -1;
    if (a.city > b.city) return 1;
    if (a.score < b.score) return 1;
    if (a.score > b.score) return -1;
    return 0;
  });
  // console.log({ Res });

  for (let i = 0; i < N; i++) {
    Res[i].printOrder = (i + 1);
  }

  // console.log({ Res });
  let Ans = [];
  for (let i = 0; i < N; i++) {
    Ans.push(Res[i].souceOrder);
  }


  console.log(Ans.join('\n'));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll int find_sum(ll int n)
{
    if (n % 2 == 0) 
      return (n/2) * (n+1); 
   else 
      return  ((n + 1) / 2) * n;
}
int main()
{
    ll int n;
    cin>>n;
    cout<<find_sum(n-1);
}

Measured memory_bytes: 256
checklis = [5,7,5,7,7]
def check(S):
    b = 0
    index = 0
    for s in S:
        b += len(s)
        if checklis[index] == b:
            index += 1
            b = 0
            if index == 5:
                return True
        elif checklis[index] > b:
            continue
        else:
            return False
    return False

def main(n):
    s = [input() for i in range(n)]
    for i in range(n):
        if check(s[i:]):
            print(i + 1)
            return

while 1:
    n = int(input())
    if n == 0:
        break
    main(n)


Measured memory_bytes: 5612
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin);i>(end);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=(" <<; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << ")" << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
#define f first
#define s second
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
ll mod = 1000000007;


int main()
{
	// 入力
	string S;
	cin>>S;
	ll s=S.size();
	ll num1=0;
	ll num0=0;
	REP(i,s){
		if(S[i]=='1') num1++;
		else num0++;
	}

	cout<<min(num1,num0)*2<<endl;


	return 0;
}

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

int main() {
    long long int sum = 0;
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); ++i) {
        sum += s[i] - '0';
    }
    cout << ((sum%9 == 0)?"Yes":"No") << '\n';
}


Measured memory_bytes: 3752
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    
    while(true){
        getline(cin, s);
        if(s == "END OF INPUT") break;

        //cout << s.size() << endl;
        int count = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ' '){
                cout << count;
                count = 0;
            }
            else count++;
        }
        cout << count << endl;
    }  
}



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

namespace ABC149B
{
    class Program
    {
        static void Main(string[] args)
        {
            var ABK = Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray();
            var A = ABK[0];
            var B = ABK[1];
            var K = ABK[2];

            long ansA, ansB;

            if (A >= K)
            {
                ansA = A - K;
                ansB = B;
            }
            else
            {
                ansA = 0;
                ansB = Math.Max(0, B - (K - A));
            }

            Console.WriteLine($"{ansA} {ansB}");
        }
    }
}

Measured memory_bytes: 13396
#include<stdio.h>
#include<math.h>
int prime[1000000]={0};
int main()
{

    int n,i,j;
    while(scanf("%d",&n)!=EOF)
    {
        int counter=0;
        for(i=4;i<=n;i+=2)
            prime[i]=1;
        for(i=3;i<=sqrt(n);i+=2)
        {
                if(prime[i]==0)
                    for(j=i*i;j<=n;j+=i*2)
                        prime[j]=1;
        }
        for(i=2;i<=n;i++)
        {
            if(prime[i]==0)
                counter++;
        }
        printf("%d\n",counter);
    }
    return 0;
}

Measured memory_bytes: 4496
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define mp make_pair
#define S second
#define F first
ll mod=1e9+7 ;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define input_from_file  freopen("input.txt", "r", stdin);
using namespace std::chrono; 

int main()
{
  // input_from_file
  ll n,x,y,z;cin>>n;string s;cin>>s;
  ll ans=1e13;
  ll red[n],white[n];memset(red,0,sizeof(red));memset(white,0,sizeof(white));
  if(s[0]=='R') red[0]=1;
  else white[0]=1;
  for(int i=1;i<n;i++){
    red[i]=red[i-1];white[i]=white[i-1];
    if(s[i]=='R') red[i]++;
    else white[i]++;
  }
  // for(int i=0;i<n;i++)  cout<<red[i]<<" ";cout<<endl;
  // for(int i=0;i<n;i++)  cout<<white[i]<<" ";cout<<endl;
  ll w_frw,w_bkw,r_bkw,r_frw,ctr=0;
  ans=min(red[n-1],white[n-1]);
  for(int i=0;i<n;i++){
    ctr=0;
    w_bkw =white[i]       ,r_bkw=red[i];
    w_frw =white[n-1]-white[i] ,r_frw =red[n-1]-red[i];
    x=min(w_bkw,r_frw);
    y=r_frw-x;
    // cout<<"x_inti="<<x<<" ,";
    x+=(i+1)-(red[i]+x);
    // cout<<"i="<<i<<" ,x="<<x<<" ,y="<<y<<endl;
    ans=min(ans,x+y);
  }
  cout<<ans;
  return 0;
}


Measured memory_bytes: 6876
// D

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll mod=1e9+7;
#define pa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
int nlx[4] = {0,0,1,-1};
int nly[4] = {1,-1,0,0};

int main(){
  int H,W;
  cin>>H>>W;
  vector<string> S(H);
  for (int i(0);i<H;i++) cin>>S[i];

  vector<int> ans;

  for (int sx(0);sx<W;sx++){
    for (int sy(0);sy<H;sy++){
      for (int gx(0);gx<W;gx++){
        for (int gy(0);gy<H;gy++){
          //cout << sx << sy << gx << gy << " ";
          if (S[sy][sx] == '#' || S[gy][gx] == '#' || (gx == sx && sy == gy)) continue;
          vector<string>s = S;
          int cnt[20][20]={0};
          s[sy][sx]='s';
          s[gy][gx]='g';
          queue <pair<int,int>> q;
          q.push({sx,sy});
          bool flag = true;
          while(!q.empty() && flag){
            pair<int,int> now = q.front();
            q.pop();
            if (s[now.second][now.first]=='#') continue;
            //cout << now.first << " " << now.second<< endl;
            s[now.second][now.first]='#';
            for (int i(0);i<4;i++){
              pair<int,int> next = {now.first + nlx[i],now.second+nly[i]};
              if (next.first < 0 || next.first >= W || next.second < 0 || next.second >= H) continue;
              cnt[next.second][next.first] = cnt[now.second][now.first]+1;
              if (next.first == gx && next.second == gy){
                ans.push_back(cnt[next.second][next.first]);
                //cout << cnt[next.second][next.first] << endl;
                flag = false;
              }
              q.push(next);
            }
          }
        }
      }
    }
  }
  int ansi(0);
  for (int i(0);i<ans.size();i++){
    ansi = max(ans[i],ansi);
  }
  cout << ansi << endl;
  return 0;
}


Measured memory_bytes: 1404
package main

import (
	"fmt"
	//"math"
)

func main() {
	var n int
	fmt.Scan(&n)
	var nums []int
	var num int
	for i := 0; i < n; i++ {
		fmt.Scan(&num)
		nums = append(nums, num)
	}
	count := 0
	for i := 1; i < n-1; i++ {
		if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) || (nums[i-1] > nums[i] && nums[i] > nums[i+1]){
			count++
		}
	}
	fmt.Print(count)
}

Measured memory_bytes: 512