akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

bool used[55][55];
int h,w;
int a[55][55];
void dfs(int x,int y){
    REP(i,-1,2)REP(j,-1,2){
        int nx=x+i,ny=y+j;
        if(nx<0||nx>=h||ny<0||ny>=w)continue;
        if(used[nx][ny]||a[nx][ny]==0)continue;
        used[nx][ny]=1;
        dfs(nx,ny);
    }
}

void solve(){
    rep(i,h)rep(j,w)cin>>a[i][j];
    rep(i,h)rep(j,w)used[i][j]=false;
    int ans=0;
    rep(i,h)rep(j,w){
        if(used[i][j]||a[i][j]==0)continue;
        ++ans;
        used[i][j]=1;
        dfs(i,j);
    }
    cout<<ans<<endl;
}
int main(){
    while(cin>>w>>h,w!=0)solve();
    return 0;
}


Measured memory_bytes: 3284
#include <stdio.h>
#include<string.h>
int main(void){
    char s1[10],s2[10],s3[10];
    scanf("%s%s%s",s1,s2,s3);
    s1[0]-=32;s2[0]-=32;s3[0]-=32;
    printf("%c%c%c",s1[0],s2[0],s3[0]);
    return 0;
}

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

int main()
{
	// ?????°??£?¨?
	int W;
	int H;
	int x;
	int y;
	int r;

	// ??\???
	cin >> W >> H >> x >> y >> r;

	// ?????¶??????
	if (((x - r) >= 0) && ((x + r) <= W) && ((y - r) >= 0) && ((y + r) <= H))
	{
		// ??????
		cout << "Yes" << endl;
	}
	else
	{
		// ??????
		cout << "No" << endl;
	}

	return 0;
}

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

uint64_t toInt(string s,int s_index,int e_index){
    uint64_t num=0;
    for(int k=s_index;k<=e_index;k++){
        num*=10;
        num+=s.at(k)-'0';
    }
    //cout<<num<<endl;
    return num;
}

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

    uint64_t sum=0;
    rep(i,0,(1<<s.size()-1)){
        bitset<10> b(i);
        int s_index=0;
        rep(j,0,s.size()){
            if(b.test(j)){
                sum+=toInt(s,s_index,j);
                s_index=j+1;
            }
        }
        sum+=toInt(s,s_index,s.size()-1);
    }
    cout<<sum<<endl;
}

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

template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

long long dp[100010][3];

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

  long long a[100010][3];
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> a[i][j];
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        if (j == k) continue;
        chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
      }
    }
  }

  long long res = 0;
  for (int i = 0; i < 3; i++) {
    chmax(res, dp[N][i]);
  }

  cout << res << endl;
}


Measured memory_bytes: 4992
def count(st):
    n=len(st)
    tmp=1
    res=[]
    for i in range(n-1):
        if st[i]==st[i+1]:
            tmp+=1
        else:
            res.append(tmp)
            tmp=1
    res.append(tmp)
    return res
S=input()
K=int(input())
T=S*3
N=len(S)
if N==1:
    print(K//2)
    exit()
if K<=2:
    Y=count(S*K)
    ans=0
    for i in Y:
        ans+=i//2
    print(ans)
    exit()
if S.count(S[0])==N:
    print((N*K)//2)
    exit()
X=[]
if S[0]==S[-1]:
    for j in range(1,N):
        if S[j-1]!=S[j]:
            break
    tmp=1
    for i in range(j,j+N-1):
        if T[i]==T[i+1]:
            tmp+=1
        else:
            X.append(tmp)
            tmp=1
    X.append(tmp)
else:
    X=count(S)

cnt=0
for i in X:
    cnt+=i//2
Y=count(T)
cnt2=0
for i in Y:
    cnt2+=i//2
print(cnt*(K-3)+cnt2)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pii pair <int,int>
#define pll pair <ll,ll>
#define testcase() int t; cin>>t; while(t--)
#define forn(i,n) for(int i=0;i<n;i++)
#define forn1(i,n) for(int i=1;i<=n;i++)
#define vll vector <ll>
#define vi vector <int>
#define all(v) v.begin(),v.end()

ll M = 1e9 + 7;
double pi = acos(-1.0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll powerm(ll x,ll y){ ll res=1; while(y){ if(y&1) res=(res*x)%M; y=y>>1; x=(x*x)%M;} return res%M; }
ll power(ll x,ll y){ ll res=1; while(y){ if(y&1) res=(res*x); y=y>>1; x=(x*x);} return res; }
ll gcd(ll a,ll b){if(b>a)return gcd(b,a); if(b==0)return a; return gcd(b,a%b);}

int main() {
	
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	
	ll d,t,s; cin>>d>>t>>s;
	if( s*t >= d ) cout<<"Yes\n";
	else cout<<"No\n";

	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<long long, long long>
#define ff first
#define ss second

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t; cin >> s >> t;
    int ans = 0, N = s.size();
    for(int i = 0; i < N; i++) ans += (s[i] != t[i]);
    cout << ans;
}

Measured memory_bytes: 3796
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i < (n);i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define SCANF(i) int i;scanf("%d",&i)
typedef long long ll;
using namespace std;
using P = pair<int,int>;
const long long INF = 1LL << 60;
const int IINF=100000000;
const int MOD = (int)1e9 + 7;
//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    //sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
vector<int> dx={1,0,-1,0};vector<int> dy={0,-1,0,1};

signed main () {
    ll a,b,c;cin >> a >> b >> c;
    ll s = b*c;
    if(a<=s)cout << "Yes" << endl;
    else cout << "No" << endl;
}//https://atcoder.jp/contests/abc177/tasks/abc177_a

Measured memory_bytes: 3656
#include <iostream>
#include <vector>

using namespace std;
int main(){
  int N,T;
  cin>>N>>T;
  vector<long> times(N);
  for(auto &t:times) cin>>t;
  long space = 0;
  long endt;
  int i=0;
  while(i<N){
    do{
      endt = times[i]+T;
      i++;
    }while(i<N&&endt>times[i]);
    if(i>=N) break;
    space += times[i]-endt;
  }
  cout<<times[N-1]+T-space<<endl;

  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reprl(i, n) for(ll i = n; i >= 0; i--)
#define fori(i, m, n) for(int i = m; i < (int)n; i++)
#define forl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define all(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
const string btos(bool ans){
  return (ans?"Yes":"No");
}
int countBits(int in){
  int res=0;
  for(int i=0;i<15;i++){
    int msk=1<<i;
    if((in&msk)!=0){
      res++;
    }
  }
  return res;
}
int main() {
  int n;cin>>n;
  vector<vector<P>> in(n);
  rep(i,n){
    int a;cin>>a;
    vector<P> alist(a);
    rep(j,a){
      P xy;
      cin>>xy.first>>xy.second;
      xy.first--;
      xy.second;
      alist[j]=xy;
    }
    in[i]=alist;
  }
  int ans=0;
  rep(i,1<<n){// Honest or Unkindの全パターン
    bool checker=true;
    rep(j,n){// N人の証言をチェック
      int ish=(i>>j)&0x01;
      if(!ish){// パターンiでHonestの証言だけ見る
        continue;
      }
      rep(k,in[j].size()){// jさんの証言を全て見る
        int person=in[j][k].first;
        int HorU=in[j][k].second;
        if(((i>>person)&0x01)==HorU){//jさんのpersonに関する証言がiと一致していればOK
          continue;
        }
        // 一致していなければ
        checker=false;
        break;
      }
      if(!checker){
        break;
      }
    }
    if(checker){
      int cnt=countBits(i);
      ans=max(ans,cnt);
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
def fragOptimalJump(h,n):
    dp=[0]*(n+1)
    dp[2]=abs(h[1]-h[2])
    for i in range(3,n+1):
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
    return dp[n]
  
N=int(input())
read = [int(n) for n in input().split()]
H=[0]+read
print(fragOptimalJump(H,N))

Measured memory_bytes: 13708
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define mem( f, x ) memset( f, x, sizeof( f ) )
#define pii pair<int, int>
#define fi first
#define se second
#define mk(x, y) make_pair( x, y )
#define pk push_back
using namespace std;
const int M = 2*1e5 + 5;
const int N = 2*1e5 + 5;
int m, n;
int color[N];
int head[N], cnt;
int son[N], cnt_color[N]; //son:子节点数量 cnt_color[i]: 以颜色i为根的子树结点数量
ll ans[N];

ll cal( ll x ){
    return x*(x+1)/2;
}

struct eg{
    int to, pre;
    eg(){ to = pre = 0; }
    eg( int tt, int pp ){
        to = tt, pre = pp;
    }
}e[2*M];

void add( int x, int y ){
    e[++cnt] = eg( y, head[x] );
    head[x] = cnt;
}

void init( ){
    ll tmp = cal( n );
    for( int i = 1; i <= n; i++ ){
        head[i] = son[i] = cnt_color[i] = 0;
        ans[i] = tmp;
    }
    cnt = 0;
}

void dfs( int cur, int fa ){
    son[cur] = 1;
    ll cur_c = color[cur];
    ll pre = cnt_color[cur_c]; //pre：遍历到cur结点之前统计到了多少以颜色cur_c为根的结点
    for( int i = head[cur]; i; i = e[i].pre ){
        int to = e[i].to;
        if( to == fa ) continue;
        //注：这里的tmp不能直接用上面的pre替换，
        //一个子节点遍历完后，可能会改变sum[cur_c]的值
        ll tmp = cnt_color[cur_c];
        dfs( to, cur );
        son[cur] += son[to];
        ll dt = cnt_color[cur_c]-tmp;
        ans[cur_c] -= cal( son[to]-dt );
    }
    //cur的子节点必定以颜色cur_c为根，前面统计到的pre加上新加的son[cur]更新sum[cur]
    cnt_color[cur_c] = pre+son[cur];
}

int main( ){
    while( scanf( "%d", &n ) != EOF ){
        init( );
        for( int i = 1; i <= n; i++ )
            cin >> color[i];
        int x, y;
        for( int i = 1; i < n; i++ ){
            cin >> x >> y;
            add( x, y );
            add( y, x );
        }
        dfs( 1, 0 );
        for( int i = 1; i <= n; i++ ){
            ans[i] -= cal( n-cnt_color[i] );
            cout << ans[i] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 30204
#include <stdio.h>

int main(int argc, char *argv[])
{
	int X, A, B;
	scanf("%d %d %d", &X, &A, &B);

	if ( B-A <= 0 ){
		printf("delicious\n");
	} else if ( B-A <= X ){
		printf("safe\n");
	} else {
		printf("dangerous\n");
	}
	return 0;
}


Measured memory_bytes: 128
// Copyright 2020 yaito3014
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
int main() {
  using namespace std;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int K;
  cin >> K;
  string S;
  cin >> S;
  const int N = K + S.length();
  constexpr int kMod = 1000000007;
  auto modpow = [&](long long a, int b) {
  	long long r = 1;
  	for (; b > 0; b /= 2) {
  		if (b % 2) r = r * a % kMod;
  		a = a * a % kMod;
  	}
  	return r;
  };
  auto inv = [&](int a) { return modpow(a, kMod - 2); };
  vector<long long> fact(N + 1, 1);
  for (int i = 0; i < N; ++i) fact[i + 1] = fact[i] * (i + 1) % kMod;
  auto c = [&](int n, int r){
  	return fact[n] * inv(fact[n-r] * fact[r] % kMod) % kMod;
  };
  int ans = 0;
  for (int i = 0; i <= K; ++i) {
  	ans += modpow(26, i) * c(N-i-1, N-K-1) % kMod * modpow(25, K-i) % kMod;
  	ans %= kMod;
  }
  cout << ans << '\n';
}


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

using namespace std;
typedef long long ll;
int main() {
    ll a, b, k;
    cin >> a >> b >> k;
    auto temp = min(a, k);
    a = a - temp;
    k = k - temp;

     temp = min(b, k);

    b = b - temp;
    cout << a << " " << b << endl;
    return 0;


}




Measured memory_bytes: 256
#include <iostream>
#include <climits>
#define ll long long
using namespace std;

ll solve(ll w[], ll v[], ll n, ll W){
    ll dp[n+1][W+1];
    for(ll i=0;i<=n;i++){
        for(ll j=0;j<=W;j++){
            if(i==0 || j==0){
                dp[i][j] = 0;
            }
            else{
                if(j>=w[i-1]){
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]);
                }
                else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
    }
    return dp[n][W];
}


int main() {
    ll n, W;
    cin >> n>>W;
    ll v[n], w[n];
    for(ll i=0;i<n;i++){
        cin >> w[i] >> v[i];
    }
    cout << solve(w, v, n, W)<< endl;
    return 0;    
}

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

using namespace std;

int main()
{
	int a, b, c;
	
	cin >> a;
	cin >> b;
	cin >> c;
	
	if(a < b && a < c){
		
		cout << "Yes" << endl;
	}
	else{
		
		cout << "No" << endl;
	}
	
    return 0;
}

Measured memory_bytes: 1156
import sys
import array

from operator import itemgetter

def main():



	input = sys.stdin.readline


	md = 998244353
	n = int(input())
	tl=n+1
	
	ft=[0]*tl

	xy = [[0]*2 for _ in range(n)]
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def upd(i):
		i+=1
		while(i<=n):
			ft[i]+=1
			i+=i&-i

	def get(i):
		i+=1
		ret=0
		while(i!=0):
		    ret+=ft[i]
		    i-=i&-i
		return ret

	def calc(get,upd):
		for i, y in enumerate(yxi):
			v = get(y); upd(y)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(get,upd))+n*cnt[n] - n)%md)

main()


Measured memory_bytes: 75028
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int main() {
	int h, w, n;
	scanf("%d%d%d", &h, &w, &n);
	int ans = INT_MAX;
	for (int i = 0; i <= h; ++i)
		for (int j = 0; j <= w; ++j) {
			int tot = h * w - (h - i) * (w - j);
			if (tot >= n) ans = min(ans, i + j);
		}
	printf("%d\n", ans);
}


Measured memory_bytes: 256
import java.io.*;
class Main
{
    public static void main(String args[])throws IOException
    {
	BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
	String str;
	int a[]=new int[26];
	while((str=input.readLine())!=null)
	    {
		
		for(int j=0;j<26;j++)
		    {	
			
			for(int i=0;i<str.length();i++)
			    {
				
				
				if((char)('A'+j)==str.charAt(i) || (char)('a'+j)==str.charAt(i))a[j]++;
				
			    }
			
		    }

	    }
	for(int j=0;j<26;j++)
	    {
	System.out.println((char)('a'+j)+" :"+" "+a[j]);
	    }
    }
}

Measured memory_bytes: 18696
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

signed main(){
    int N;
    int a[100];

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

    int ans=LLONG_MAX;
    for(int i=-200;i<=200;i++){
        int c=0;
        for(int j=0;j<N;j++){
            c+=abs((i-a[j])*(i-a[j]));
        }
        ans=min(c,ans);
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 3132
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
//#define MOD 1000000007
#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int main(){
    int x; cin >> x;
    int k = lcm(x,360);
    int ans = k/x;
    cout << ans << endl;
}



Measured memory_bytes: 3672
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rrep(i, n) for(ll i = n - 1; i > -1; i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
#define debug(V) rep(i, V.size()) cout << V[i] << " ";
const ll INF = (1LL << 61) - 1;
const ll MOD = 1000000007 /*998244353*/;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, h, x, y, z, p, q, m, n, t, r, k, w, l, ans, i, j;
string S, T;
vl A, B;
long double P;
void solve() { cout << ll(a * P) << endl; }
int main() {
    // cout << fixed << setprecision(18);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> a;
    cin >> P;
    solve();
}

Measured memory_bytes: 3752
#include <cstdio>
#include <algorithm>
#include <bitset>
#define MAXN 50005
#define MAXBS 70005
using namespace std;
bitset<MAXBS> bs;
int a[MAXN];
int main(void){
    int n,k;
    int ll,rr;
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    sort(a+1,a+n+1);
    //Min Necessary:[ll,rr]
    ll=0,rr=n+1;
    while (rr>ll){
        int mid=(ll+rr)>>1;
        int necessary=0;
        if (a[mid]>=k){
            rr=mid;
            continue;
        }
        bs.reset(); // bs=0
        bs.set(0); // bs[0]=1;
        for (int i=1;i<=n;i++)
            if (i!=mid)
                bs|=(bs<<a[i]);
        for (int i=k-1;i>=k-a[mid];i--){
            if (bs.test(i)){
                necessary=1;
                break;
            }
        }
        if (necessary)
            rr=mid;
        else
            ll=mid+1;
    }
    printf("%d",ll-1);
    return 0;
}

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

#define F first
#define S second

using namespace std;

long long int mod = 1e9+7, lg = 100;

long long int wop(long long int x, long long int y) {
    if(y==0)return 1;
    long long int ret=wop(x,y/2);
    ret=(ret*ret)%mod;
    if(y&1)ret*=x;
    return ret%mod;
}

/*long long int chos(long long int r, long long int n) {
    return fac[n]*rev[r]*rev[n-r]
}*/

const int N = 1e5+100, M = 25;
long long int a[M], b[M], pw[M];
vector<long long int> vn1, vn2;
int fac[N], inv[N];
 
int pwpw(int x, int y) {
	if(y == 0)
		return 1;
	int cnt = pwpw(x, y / 2);
	cnt = (cnt * cnt) % M;
	cnt = (cnt * (y % 2 == 1 ? x : 1)) % M;
	return cnt;
}
 
void prepro() {
	fac[0] = 1;
	for(int i = 1; i <= N - lg; i++) 
		fac[i] = (fac[i - 1] * i) % M;
	inv[N - lg] = pwpw(fac[N - lg], M - 2);
	for(int i = N - lg - 1; i > -1; i--) 
		inv[i] = (inv[i + 1] * (i + 1)) % M;
}
 
int c(int x, int y) {
	return ((fac[x] * inv[y] % M) * inv[x - y]) % M;
}
 

int main () {
    ios::sync_with_stdio(0);
    prepro();
int k = 0;
for(int i = 0; i < N; i++) {
	k += i;
	k %= N;
}
k/= 1001293;
for(int i = 0; i < 10; i++) {
	for(int j = 0; j < 10; j++) {
		k += 1011;
		k %= N;
	}
}
k /= 10;
for(int i = 0; i < 10100; i++)
	k = (k + 1) % 101000;
k /= 100;
k = 0;
	pw[0]=1;
    for(int i = 1 ; i < 20 ; i++)pw[i]=pw[i-1]*2;
    long long int n;
    cin >> n;
    for(int i = 0 ; i < n ; i ++ ) {
        cin >> a[i];
    }
    for(int i = 0 ; i < n ; i ++ ) {
        cin >> b[i];
    }
    long long int ans=1e18;
    for(int i = 0 ; i < pw[n] ; i++ ) {
        vector<long long int> v;
        v.clear();
        long long int com[n+4][4];
        memset(com,63,sizeof(com));
        for(int j = 0 ; j < n ; j++ ) {
            if(i&pw[j]) {
                v.push_back(b[j]);
                com[j][1]=b[j];
            }
            else {
                v.push_back(a[j]);
                com[j][0]=a[j];
            }
        }
        sort(v.begin(),v.end());
        long long int mas=0;
        bool adm=0;
        for(int p = n-1 ; p>= 0 ;p--) {
            bool ok=0;
            for(int j = p ; j >= 0 ; j--) {
                if((p-j)%2==0) {
                    if(com[j][0]==v[p]) {
                        for(int k = j ; k < p ; k++) {
                            swap(com[k][0],com[k+1][1]);
                            swap(com[k][1],com[k+1][0]);
                            mas++;
                        }
                        ok=1;
                    }
                }
                else {
                    if(com[j][1]==v[p]) {
                        for(int k = j ; k < p ; k++) {
                            swap(com[k][0],com[k+1][1]);
                            swap(com[k][1],com[k+1][0]);
                            mas++;
                        }
                        ok=1;
                    }
                }
                if(ok)break;
            }
            if(!ok) {
                adm=1;
                break;
            }
        }
        if(!adm) {
            ans=min(ans,mas);
        }
    }
    if(ans>1e9) return cout << -1,0;
    cout << ans;
}

Measured memory_bytes: 1152
public class Main {
	
	public void run(java.io.InputStream in, java.io.PrintStream out) {
		final java.util.Scanner sc = new java.util.Scanner(in);
		long[][] a;
		long[][] b;
		long[][] r;
		int n, m, l;

		n = sc.nextInt();
		m = sc.nextInt();
		l = sc.nextInt();
		a = new long[n][m];
		b = new long[m][l];
		for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			a[i][j] = sc.nextLong();
		}
		for (int i = 0; i < m; ++i)
		for (int j = 0; j < l; ++j){
			b[i][j] = sc.nextLong();
		}
		
		r = new long[n][l];
		for (int i = 0; i < n; ++i)
		for (int j = 0; j < l; ++j) {
			r[i][j] = 0;
			for (int k = 0; k < m; ++k) {
				r[i][j] += a[i][k] * b[k][j];
			}
		}
		
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < l; ++j) {
				out.print(r[i][j]);
				if (j + 1 == l) out.println();
				else out.print(" ");
			}
		}
				
		sc.close();
	}

	public static void main(String[] args) {
		(new Main()).run(System.in, System.out);
	}

}

Measured memory_bytes: 54956
/*input
3 5 7
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=4e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
ll mult(ll a,ll b){
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int a,b,t;
    cin>>a>>b>>t;
    int ans=0;
    REP1(i,t){
        if(i%a==0) ans+=b;
    }
    cout<<ans;
}

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

int main(){
    string s,t;
    cin>>s>>t;
    string success_flag = "No";
    string temp_s = s;
    for (int i=0;i<s.length();i++){
        temp_s = temp_s[s.length() - 1] + temp_s.substr(0, s.length() - 1);
        if (temp_s == t){
            success_flag = "Yes";
            break;
        }
        
    }
    cout<<success_flag<<endl;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<string>> a(H,vector<string>(W));
  string tmp;
  for (int i = 0; i < H; i++) {
    cin >> tmp;
    for(int j=0;j<W;j++){
      a.at(i).at(j)=tmp.at(j);
    }
  }
  bool isW=true;
  for(int i=0;i<H;i++){
    isW=true;
    for(int j=0;j<W;j++){
      if(a.at(i).at(j)=="#"){
        isW=false;
      }
    }
    if(isW){
      for(int j=0;j<W;j++){
        a.at(i).at(j)="V";
      }
    }
  }
  for(int i=0;i<W;i++){
    isW=true;
    for(int j=0;j<H;j++){
      if(a.at(j).at(i)=="#"){
        isW=false;
      }
    }
    if(isW){
      for(int j=0;j<H;j++){
        a.at(j).at(i)="V";
      }
    }
  }
  bool isWrite=false;  
for(int i=0;i<H;i++){
  isWrite=false;
  for(int j=0;j<W;j++){
    if(a.at(i).at(j)=="V"){
      continue;
    }else{
      cout << a.at(i).at(j);
      isWrite=true;//その行になんか書いたか
    }
  }
  if(isWrite)  cout << endl;
}



}


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


ll dp[105][2][105];

int main() {
  string N;
  ll K;
  cin >> N >> K;
  dp[0][0][0] = 0;
  dp[0][0][1] = 1;
  dp[0][1][0] = 1;
  dp[0][1][1] = N[0]-'1';
  REP(i,N.length()+1) {
    REP(j,101) {
      dp[i+1][1][j+1] += dp[i][1][j] * 9;
      dp[i+1][1][j+1] += dp[i][0][j] * max((N[i+1]-'1'),0);
      dp[i+1][1][j]   += dp[i][1][j];
      if (N[i+1] == '0') {
        dp[i+1][0][j]   += dp[i][0][j];
      } else {
        dp[i+1][1][j]   += dp[i][0][j];
        dp[i+1][0][j+1] += dp[i][0][j];
      }
    }
  }
  cout << (dp[N.length()-1][0][K] + dp[N.length()-1][1][K] ) << endl;

//  REP(i,3) REP(j,3) REP(k,2) cout << "  [" << i << "][" << k  << "][" << j << "] : " <<  dp[i][k][j] << endl;
}



Measured memory_bytes: 384
#include <iostream>

using namespace std;

int rewards[] = {0, 300000, 200000, 100000};
const int bothr = 400000;

int main()
{
  int x, y;
  cin >> x >> y;
  int ans = 0;
  if (x <= 3)
    ans += rewards[x];
  if (y <= 3)
    ans += rewards[y];
  if (x == 1 && y == 1)
    ans += bothr;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include<iomanip>
using namespace std;

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

    vector<long long> counter;
    int count = 0;
    for(int i=0;i<N-1;i++)
    {
        if(H[i]>=H[i+1])
        {
            count++;
        }
        else
        {
            
            counter.push_back(count);
            count = 0;
        }
    }
    counter.push_back(count);
    long long max = *std::max_element(counter.begin(), counter.end());
    cout<<max<<endl;
}

Measured memory_bytes: 2168
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#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) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1e9 + 7;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    set<char> st;
    rep(i, 0, N) {
        char c;
        cin >> c;

        st.insert(c);
    }
    if (st.size() == 3) {
        cout << "Three" << endl;
    } else {
        cout << "Four" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
<?php
/*
    Problem URL : https://beta.atcoder.jp/contests/abc067/tasks/abc067_b

    Score  :
    Result :
    Time   : ms
    Memory : KB
 */

// define('DEBUG', true);
define('DEBUG', false);

ini_set('error_reporting', E_ALL & ~E_NOTICE);

fscanf(STDIN, "%d %d", $N, $K);
$a = explode(" ", trim(fgets(STDIN)));

rsort($a);

$ans = 0;
for ($i = 0; $i < $K; $i++) {
    $ans += $a[$i];
}

echo $ans . PHP_EOL;


Measured memory_bytes: 4604
#include <iostream>
int main(){
  int a[3];
  int t=1000;
  std::cin >> a[0] >> a[1] >> a[2];
  for(int i=0;i<3;i++){
      for(int j=0;j<3;j++){
          if (i!=j)
              t =  (t < (a[i] + a[j])) ? t : (a[i] + a[j]);
      }
  }
  std::cout << t;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
routes=list(map(int,input().split()))
dp=[float("inf") for i in range(n)]
dp[0]=0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j<n:
            dp[j]=min(dp[j],dp[i]+abs(routes[i]-routes[j]))


print(dp[-1])

Measured memory_bytes: 88832
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

string solve(string& s) {
	for (int i = 0; i < 26; ++i) {
		bool found = false;
		for (int j = 0; j < s.length(); ++j)
			found |= s[j] == ('a' + i);
		if (!found) {
			string res = "a";
			res[0] = (res[0] + i);
			return res;
		}
	}
	for (int i = 0; i < 26; ++i) {
		for (int j = 0; j < 26; ++j) {
			string tmp = "aa";
			tmp[0] = (tmp[0] + i);
			tmp[1] = (tmp[1] + j);
			bool found = false;
			int ptr = 0;
			for (int k = 0; k < s.length(); ++k) {
				if (s[k] == tmp[ptr]) {
					++ptr;
					if (ptr == 2) {
						found = true;
						break;
					}
				}
			}
			if (!found)
				return tmp;
		}
	}
}

int main() {
	string A; cin >> A;
	int f = 0;
	vector<string> A_part;
	string tmp = "";
	for (int i = A.length() - 1; i >= 0; --i) {
		tmp = A[i] + tmp;
		f |= (1 << (A[i] - 'a'));
		if (f == (1 << 26) - 1) {
			A_part.push_back(tmp);
			f = 0; tmp = "";
		}
	}
	A_part.push_back(tmp);

	reverse(A_part.begin(), A_part.end());

	string res = solve(A_part[0]);
	string lst_added = res;
	for (int i = 1; i < A_part.size(); ++i) {
		int ptr = 0;
		int idx = 0;
		while (i < A_part.size() && ptr < lst_added.length()) {
			while (idx < A_part[i].length() && A_part[i][idx++] != lst_added[ptr]);
			if (A_part[i][idx - 1] == lst_added[ptr])
				++ptr;
			else {
				++i; idx = 0;
			}
		}
		if (i == A_part.size()) break;
		string tmp = A_part[i].substr(idx, A_part[i].length() - idx);
		res += (lst_added = solve(tmp));
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 1028
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int left = 0;
        int count = 0;

        while (left < arr.length) {
            if (arr[left] == 0) left++;
            else {
                int right = left;

                while (right < arr.length && arr[right] != 0) {
                    arr[right++]--;
                }
                count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 23764
#include<iostream>
#include<cstring>
using namespace std;
string a;
int s,e;
int main()
{
    cin>>a;
    for(int i=0;i<a.length();i++)
        if(a[i]=='A')
        {
            s=i;
            break;
        }
    for(int i=a.length()-1;i>=0;i--)
        if(a[i]=='Z')
        {
            e=i;
            break;
        }
    cout<<e-s+1<<endl;
    return 0; 
} 

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n,m,k,c,a=0;
    cin>>n>>m;
    vector<vector<ll>> s(m);
    for(ll i=0;i<m;i++){
        cin>>k;
        s[i].resize(k);
        for(ll j=0;j<k;j++){
            cin>>s[i][j];
            s[i][j]--;
        }
    }
    vector<ll> p(m);
    for(ll i=0;i<m;i++) cin>>p[i];
    for(ll i=0;i<(1<<n);i++){
        for(ll j=0;j<m;j++){
            c=0;
            for(auto sw:s[j]){
                if((i>>sw)&1) c++;
            }
            if(c%2!=p[j]) break;
            if(j==m-1) a++;
        }
    }
    cout<<a<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

#define MAXN (1 << 20)
#define INF (1 << 30)

int n;
int a[MAXN];

int main() {
	cout << fixed << setprecision(12);	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	a[n] = INF;
	int i = 0;
	int ret = 0;
	while (i < n) {
		int cur = 0;
		while (a[i + 1] <= a[i]) {
			i++;
			cur++;
		}
		ret = max(ret, cur);
		i++;
	}
	cout << ret << endl;
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

	mod& operator*=(const mod & m2) {
		x *= m2.x;
		x %= MOD;
		return *this;
	}

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

ostream &operator<<(ostream & os, const mod & m) {
	return os << m.x;
}



Measured memory_bytes: 4016
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
const long long MOD = 1000000007;

ll N, M;
bool adj[10][10];

signed main(){
    cin >> N >> M;
    ll a, b;
    REP(i, M){
        cin >> a >> b;
        a--; b--;
        adj[a][b] = adj[b][a] = true;
    }
    vector<ll> v(N);
    iota(ALL(v), 0);
    ll ans = 0;
    do{
        if(v[0] != 0) break;
        bool ok = true;
        REP(i, N - 1){
            if(!adj[v[i]][v[i + 1]]) ok = false;
        }
        ans += ok;
    }while(next_permutation(ALL(v)));
    PRINT(ans);
    return 0;
}

Measured memory_bytes: 3560
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//グローバル変数


//ライブラリ挿入


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

    ll r,g,b;
    r=0;
    g=0;
    b=0;
    REP(i,N){
        if(S[i]=='R') r++;
        if(S[i]=='G') g++;
        if(S[i]=='B') b++;
    }
    ll ans=r*g*b;
    int i,ii,iii;
    REP(i,N){
        REP2(j,1,N/2+1){
            ii=i+j;
            iii=ii+j;
            if(iii>N-1) break;
            if(S[i]!=S[ii]&&S[ii]!=S[iii]&&S[iii]!=S[i]) ans--;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3644
def printans(x):
  for h in range(1, H+1):
    for w in range(1, W+1):
      if w > 1:
        print(' ', end='')
      print(x[h][w], end='')
    print()
		
H, W = map(int, input().split())
N = int(input())
a = list(map(int, input().split()))
a.insert(0, -1)

g = [[-1] * (W+2) for x in range(H+2)]
v = 1
for h in range(1, H+1):
  if h%2 != 0:
    for w in range(1, W+1):
      g[h][w] = v
      a[v] -= 1
      if a[v] == 0:
        v += 1
  else:
    for w in range(W, 0, -1):
      g[h][w] = v
      a[v] -= 1
      if a[v] == 0:
        v += 1

printans(g)

Measured memory_bytes: 4596
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

N = int(input())
# S = input()
# N, M = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0

for i in range(1, N + 1) :
    if len(str(i)) % 2 == 1 :
        ans += 1
    
print(ans)



Measured memory_bytes: 39920
#include <cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<set>
#include<tuple>
#include<bitset>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
int main() {
	string s;
	cin >> s;
	ll count = 0;
	ll ma = -inf;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'R') {
			count ++;
		}
		else {
			ma = max(count, ma);
			count = 0;
		}
	}
	ma = max(count, ma);
	cout << ma << endl;
	return 0;
}

Measured memory_bytes: 3592
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0;i < (int)(n);i++)
#define RREP(i,n) for(int i = (int)n-1;i >= 0;i--)
#define FOR(i,s,n) for(int i = s;i < (int)n;i++)
#define RFOR(i,s,n) for(int i = (int)n-1;i >= s;i--)
#define ALL(a) a.begin(),a.end()
template<class T>inline void out(T t){cout<<t<<"\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout<<t<<" ";out(ts...);}
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;}
constexpr long long INF = 1e9;



signed main(){
	int N,K;
	cin>>N>>K;
	vector<double>p(N);
	REP(i,N){
		int t;
		cin >> t;
		p[i] = t * (t + 1) / 2.0 / t;
	}
	vector<double>ps(N+1);
	REP(i,N){
		ps[i+1]+=ps[i]+p[i];
	}
	double ma = 0.0;
	REP(i,N-K+1){
		double t = ps[i+K]-ps[i];
		CHMAX(ma,t);
	}
	printf("%.20f\n",ma);
}


Measured memory_bytes: 3328
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdio>
#define M 2000000000
using namespace std;
int main(void){
	int n,i,j,sum,p[5000],a[5000],mn;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>p[i];
	}
	mn=M;
	for(i=0;i<=p[0];i++){
		for(j=0;j<n;j++){
			a[j]=p[j];
		}
		a[0]=a[0]-i;
		sum=i;
		for(j=0;j<n-1;j++){
			if(a[j]>0){
				a[j+1]-=a[j];
				sum+=a[j]*2;
				a[j]=0;
			}
		}
		if(a[n-1]>0)sum+=a[n-1];
		mn=min(mn,sum);
	}
	cout<<mn<<endl;
	return 0;
}


Measured memory_bytes: 3132
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
    int n, t, a, i, ansidx;
    double ans;
    vector <int> h(1000);
    cin >> n >> t >> a;
    for(i=0;i<n;i++){
        cin >> h.at(i);
    }
    ans=abs(a-(t-(h.at(0)*0.006)));
    ansidx=1;
    for(i=1;i<n;i++){
        if(abs(a-(t-(h.at(i)*0.006)))<ans){
            ans=abs(a-(t-(h.at(i)*0.006)));
            ansidx=i+1;
        }
    }
    cout << ansidx <<endl;
    return 0;
}


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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define DBG(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define DBG(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define CIN(type, ...) \
  type __VA_ARGS__;    \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define COUT(...) write_to_cout(__VA_ARGS__);

#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

int main() {
  CIN(int,H,W);
  vector<string>m(H);
  REP(i,H)cin>>m[i];

  int ans=0;
  REP(sr,H)REP(sc,W){
    if(m[sr][sc]!='.')continue;
    queue<tuple<int,int,int>>que;
    que.push(make_tuple(sr,sc,0));
    set<pair<int,int>>seen;
    seen.insert({sr,sc});
    while(!que.empty()){
      int cr,cc,dist;
      tie(cr,cc,dist)=que.front();
      que.pop();
      ans=max(ans,dist);
      REP(d,4){
        int dr[]={0,0,1,-1};
        int dc[]={1,-1,0,0};
        int nr=cr+dr[d];
        int nc=cc+dc[d];
        if(nr<0||H<=nr||nc<0||W<=nc||m[nr][nc]!='.')continue;
        if(seen.count({nr,nc}))continue;
        seen.insert({nr,nc});
        que.push(make_tuple(nr,nc,dist+1));
      }
    }
  }
  COUT(ans);
}


Measured memory_bytes: 384
#include <cstdio>

int main() {
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  int t = 0;
  for (int i=0;i<60;i++) {
    if (c <= t+a) {
      printf("%d\n", c);
      return 0;
    }
    t += a+b;
    if (t > c) {
      do c += 60; while (t > c);
    }
  }
  puts("-1");
  return 0;
}

Measured memory_bytes: 2736
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H, N;
  cin >> H >> N;
  vector<vector<int>> vec(N,vector<int>(2));
  for(int i=0; i<N; i++){
    for(int j=0; j<2; j++){
      cin >> vec.at(i).at(j);
    }
  }
  
  int INF = 10000000000;
  
  int dp[N+1][H+10010];
  for(int i=0; i<=N; i++){
    for(int j=0; j<H+10010; j++){
      if(j == 0){
        dp[i][j] = 0;
      }
      else{
        dp[i][j] = INF;
      }
    }
  }
  
  for(int i=0; i<N; i++){
    int a = vec.at(i).at(0);
    int b = vec.at(i).at(1);
    for(int j=0; j<=H+10010; j++){
      if(j < a){
        dp[i+1][j] = dp[i][j];
      }
      else{
        dp[i+1][j] = min(dp[i][j], dp[i+1][j-a]+b);
      }
    }
  }
  
  int ans_x = INF;
  for(int j=H; j<H+10010; j++){
    ans_x = min(ans_x,dp[N][j]);
  }
  cout << ans_x << endl;
  
  /*for(int i=0; i<=N; i++){
    for(int j=0; j<H+5; j++){
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }*/
}



Measured memory_bytes: 78592
#include<iostream>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<set>
#include<string.h>
#include<ctype.h>

using namespace std;

int arr[10];
int sub[10];
int n,k;
int now = 0;
int cont;
int c = 0;

set<int> visit2;

void saiki(int[],int);

int main()
{
	for(;;)
	{
		visit2.clear();
		int i;
		c = 0;
		now = 0;
		
		scanf("%d",&n);
		scanf("%d",&k);
		if(n == 0 && k == 0){
			break;
		}
		
		for(i = 0; i < n; i++){
			scanf("%d",&arr[i]);
		}
		for(i = 0; i < n; i++){
			sub[0] = arr[i];
	//		printf("\næªJ[hF%d\n",arr[i]);
			saiki(sub,1);
			now++;
		}
		cout <<visit2.size()-c << endl;
	}
}

void saiki(int temp[], int kk)
{
	//k:TõK
	int used[50] = {0};
	int i;
	int t = 0;
	char str[256] = "";
	
	for(i = 0; i < kk; i++){
		sprintf(str+strlen(str),"%d",temp[i]);
	}
	
	t = atoi(str);
	
	if(kk == k){
		
		visit2.insert(t);
		return;
	}
	else{ 
		int j;
		
//		cout << "*t = " << t << endl;
		
		for(i = 0; i < kk; i++){
			for(j = 0; j < n; ++j ){     
				if( used[j] == 0 && arr[j] == temp[i] ){
//					printf("J[h%dÍgpÏÝ\n",arr[j]);
					used[j] = 1;
					break;
				}
			}
		}
		
		for(i = 0; i < n; i++){
			if(used[i] == 0){
				temp[kk] = arr[i];
				used[i] = 1;
				saiki(temp, kk+1);
				used[i] = 0;
			}
		}
	}
}
			

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

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

	// 幸福じゃない人たちを見る
	// 右向きの人達, 左向きの人たち
	int left = 0, right = 0;
	if(S[0] == 'L') left++;
	if(S[N-1] == 'R') right++;
	for(int i=0;i<N-1;i++) {
		if(S[i] == 'R' and S[i+1] == 'L') {
			right++;
			left++;
		}
	}
	if(left == right) {
		if(left > K) cout << N - ((left + right) - 2 * K) << endl;
		else cout << N - 1 << endl;
	} else {
		int minval = min(left, right);
		cout << N - ((left+right) - 2 * min(minval, K)) << endl;
	}
}

Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long

int max(int aa, int bb);

int main(void) {
    int a_len,b_len,itr,itrA,itrB,dp[3005][3005],tmp,piv_x,piv_y,piv_ans=0,ans_len;
    char a_str[3005],b_str[3005], ans[3005];
    scanf("%s %s",a_str,b_str);
    //配列の長さを取得
    a_len = strlen(a_str);
    b_len = strlen(b_str);
    //初期化
    for(itr = 0;itr <= a_len; itr++){
        dp[itr][0] = 0;
    }
    for(itr = 0;itr <= b_len; itr++){
        dp[0][itr] = 0;
    }
    /*
    dpの計算
    三通りあるので、それらの最大値を取る
    */
    for(itrA = 1;itrA <= a_len; itrA++){
        for(itrB = 1;itrB <= b_len; itrB++){
            dp[itrA][itrB] = max(dp[itrA][itrB-1],dp[itrA-1][itrB]);
            if(a_str[itrA-1]==b_str[itrB-1]){
                tmp = dp[itrA-1][itrB-1] + 1;
                dp[itrA][itrB] = max(dp[itrA][itrB],tmp);
            }
        }
    }
    //右下から探索を始める
    piv_x = a_len;
    piv_y = b_len;
    
    while(piv_x != 0 && piv_y != 0){
        if(dp[piv_x][piv_y] == dp[piv_x-1][piv_y]){
            piv_x--;
        }
        else if(dp[piv_x][piv_y] == dp[piv_x][piv_y-1]){
            piv_y--;
        }
        else{
            //左上なのでansに追加
            ans[piv_ans] = a_str[piv_x-1];
            piv_ans++;
            piv_y--;
        }
    }
    ans_len = strlen(ans);
    //反転しながら出力
    for(itr = ans_len-1;itr >= 0; itr--){
        printf("%c",ans[itr]);
    }
    printf("\n");
    
    return 0;
}
//maxを計算する関数
int max(int aa, int bb) {
    if (aa > bb)
        return aa;
    else
        return bb;
}


Measured memory_bytes: 35456