akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
int n,t,a[3000],b[3000];
pair<int,int> p[3000];
int dp[4000][7000]; // i個目まで、時間j以下
int main(){
    cin>>n>>t;
    for(int i=0;i<n;i++)cin>>a[i]>>b[i],p[i]=make_pair(a[i],b[i]);
    sort(p,p+n);
    for(int i=0;i<n;i++)a[i]=p[i].first,b[i]=p[i].second;
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<t;j++){
            dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
            dp[i+1][j+a[i]]=max(dp[i][j+a[i]],dp[i][j]+b[i]);
            ans=max(ans,dp[i+1][j+a[i]]);
        }
    }
    cout<<ans<<endl;
}

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

struct MatPos
{
	MatPos(int row, int col)
		: row(row)
		, col(col)
	{
	}

	int row, col;
};

int main()
{
	int w, h;
	std::cin >> h >> w;

	std::string s;
	s.reserve(w * h);
	for (int row = 0; row < h; row++)
	{
		std::string line;
		std::cin >> line;
		s.append(line);
	}

	std::vector<int> isBlacks;
	isBlacks.resize(w * h);

	std::queue<MatPos> blacks;
	for (int row = 0; row < h; row++)
	{
		for (int col = 0; col < w; col++)
		{
			if (s[col + row * w] == '#')
			{
				blacks.emplace(row, col);
				isBlacks[col + row * w] = 1;
			}
		}
	}

	auto getIndex = [&](int row, int col)
	{
		if (row < 0 || h <= row) return -1;
		if (col < 0 || w <= col) return -1;
		return col + w * row;
	};

	const std::pair<int, int> offsets[] =
	{
		{-1, 0},
		{0, -1},
		{0, 1},
		{1, 0},
	};

	int maxDist = 0;
	while (!blacks.empty())
	{
		const auto grid = blacks.front();
		blacks.pop();

		maxDist = std::max(maxDist, isBlacks[getIndex(grid.row, grid.col)]);

		for (auto offset : offsets)
		{
			const auto nextIndex = getIndex(
				grid.row + offset.first,
				grid.col + offset.second
			);

			if (nextIndex < 0)
			{
				continue;
			}
			
			if (isBlacks[nextIndex] == 0)
			{
				isBlacks[nextIndex] = isBlacks[getIndex(grid.row, grid.col)] + 1;

				blacks.emplace(
					grid.row + offset.first,
					grid.col + offset.second
				);
			}
		}
	}

	std::cout << maxDist  - 1 << "\n";
}


Measured memory_bytes: 13328
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PP pair<P,P>



ll power(ll x,ll k){
  ll ret=1;
  while(k>0){
    if(k&1) (ret*=x) %= M;
    (x*=x) %= M;
    k >>= 1;
  }
  return ret;
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  string s;
  cin>>s;
  int fl=0,fr=0,a=0,c=0;
  rep(i,s.size()){
    if(s[i]=='C') c++;
    if(s[i]=='?') fr++;
  }

  int ans=0;
  rep(i,s.size()){
    if(s[i]=='A') a++;
    else if(s[i]=='C') c--;
    else {
      if(s[i]=='?') fr--;
      int res=a*power(3,fl)%M+fl*power(3,fl-1)%M;
      res%=M;
      res*=c*power(3,fr)%M+fr*power(3,fr-1)%M;
      res%=M;
      ans+=res;
      ans%=M;
      if(s[i]=='?') fl++;
    }
    //cout<<ans<<endl;
  }

  cout<<ans<<endl;


}

Measured memory_bytes: 512
#include <stdio.h>

int main(){

    int t; //first line

    scanf("%d",&t);

    int r[t];
    int i = 0;
    int j;
    int p;


    while(i < t){
        scanf("%d",&r[i]);
        i++;
    }

    i = 0;
    p = r[1] - r[0];
    int minr = r[0];

    for(j=1; j<t; j++){
        
        if(minr > r[j-1]){
            minr = r[j-1];
        }
        
        if(p < (r[j] - minr)){
            p = r[j] - minr;
        }
    }


    printf("%d\n",p);

    return 0;

}


Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define MOD = 998244353;
#define int long long int
#define double long double
#define inf (int)(1e15)
#define all(x) (x).begin(), (x).end()
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define isYes(x) printf("%s\n", (x) ? "Yes" : "No")
#define isYES(x) printf("%s\n", (x) ? "YES" : "NO")
#define isIn(x, y, h, w) (x >= 0 && x < h && y >= 0 && y < w)
#define pair pair<int, int>
typedef vector<int> vi;   // Vector of long long
typedef vector<vi> vvi;   // Vector of vi
typedef vector<pair> vii; // Vector of pairs
typedef vector<vii> vvii; // Vector of Vector of pairs
typedef vector<bool> vb;  // Vector of bool
#define pq priority_queue // Max heap (To convert to min heap, use negative sign before every value)
#define ff first          // For pairs
#define ss second
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, -1, 0, 1};
const int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1}, dy8[] = {1, -1, 1, 0, -1, 1, -0, -1};
#define testcases(t) \
    int(t);          \
    cin >> (t);      \
    while ((t)--)
#define range(c, r) (c).begin(), (c).begin() + (r)    // Mainly used in sorting
#define present(c, x) ((c).find(x) != (c).end())      // for sets, maps, multi-maps
#define cpresent(c, x) (find(all(c), x) != (c).end()) // for vectors
#define run(x, c) for ((x) = (c).begin(); (x) != (c).end(); (x)++)
#define fo0 (i, n) for (i = 0; i < n; i++)
#define fo1 (i, n) for (i = 1; i <= n; i++)
#define rfo(i, n) for (i = n - 1; i >= 0; i--)
#define rfor(i, n) for (i = n; i > 0; i--)
signed main()
{
    int a, b, c, d, th, ah;
    cin >> a >> b >> c >> d;
    th = c / b;
    if (c % b != 0)
        th++;
    ah = a / d;
    if (a % d != 0)
        ah++;
    if (th <= ah)
        cout << "Yes" << endl;
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3588
n = int(input())
li = [list(map(int,input().split())) for _ in range(n)]

s = 1
t = 1
dis = 0

for i in range(1,n+1):
    s *= i

for j in range(1,n):
    t *= j
    
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dis += ((li[i][0] - li[j][0])**2 + (li[i][1] - li[j][1])**2)**0.5

print(t*dis/s)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
int main () {
  long N;
  cin >> N;
  vector<long> data(N);
  long a = 0;
  for(int i = 0; i < N; i++){
    cin >> data.at(i);
    a = a ^ data.at(i);
  }
  for(int i = 0; i < N; i++)cout << (a ^ data.at(i)) << ' ';
  return 0;
}

Measured memory_bytes: 4828
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define ld long double
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pi 3.141592653589793238
#define MOD 1000000007
#define INF 1000000000000000007LL


const int N = 100005;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif


void solve(){
    string s; cin>>s;
    For(i, 0, sz(s)){
        if(s[i]=='?')
            s[i]='D';
    }
    cout<<s;
}


signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int t=1; 
    // cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}



Measured memory_bytes: 3784
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long int a[200005],b[200005];
int m,n;
long long int k;
long long int ans=0,as=0,bs=0,mx=0;
int main(){
scanf("%d%d%lld",&n,&m,&k);
a[0]=b[0]=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
a[i]+=a[i-1];
if(a[i]<=k)as=i;
}
for(int i=1;i<=m;i++){
scanf("%lld",&b[i]);
b[i]+=b[i-1];
if(b[i]+a[as]<=k)bs=i;
}
mx=max(mx,as+bs);
for(int i=as-1;i>=0;i--){
while(bs+1<=m&&b[bs+1]+a[i]<=k){
bs++;
}
mx=max(i+bs,mx);
}
printf("%lld",mx);
}

Measured memory_bytes: 4844
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
#define ll long long

using namespace std;

int main(){
    ll N,M,a,b;
    cin >> N >> M;

    vector <bool> kara1(N+1,false);
    vector <bool> ikiN(N+1,false);
    string res = "IMPOSSIBLE";
    REP(i,M)
    {
        cin >> a >> b;
        if(a == 1)
        {
          kara1[b] = true;
        }
        if(b == N)
        {
          if(a == 1)
          {
            res = "POSSIBLE";
            break;
          }
          ikiN[a] = true;
        }
    }

    REP(i,N+1)
    {
      if(kara1[i] == true && ikiN[i] == true)
      {
        res = "POSSIBLE";
        break;
      }
    }

    cout << res << endl;

    return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long int
#define fi first
#define se second
#define pub push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for(int i=(int)(l);i<(int)(r);i++)
#define repd(i, l, r) for (int i=(int)(l);i>=(int)(r);i--)
#define clrg(i, l, r) for(int i=(int)(l);i<(int)(r);i++)vis[i]=0,v[i].clear();
int power(int x, unsigned int y){int res = 1;while (y > 0){ if (y & 1){res = res*x;} y = y>>1;x = x*x;}return res;}
int powermod(int x, unsigned int y, int p){int res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}return res;}
#define print2d(mat,n,m){for(int i=0;i<(int)(n);i++){for(int j=0;j<(m);j++){cout<<mat[i][j]<<" ";}cout<< endl;}}
#define clr(a,x) memset(a,x,sizeof(a))
#define rr(v) for(auto &val:v)
#define print(v) for (const auto itr : v){cout<<itr<<' ';}cout<<"\n";
#define ln length()
#define sz size()
#define mod 1000000007
#define elif else if
int32_t main(){
    int n,d; cin>>n>>d;
    int ans=0;
    rep(i,0,n){
      int a,b;
      cin>>a>>b;
      a=llabs(a);
      b=llabs(b);
      int di=a*a+b*b;
     // cout<<di<<"\n";
      if(di<=d*d)ans++;
    }
    cout<<ans<<"\n";
   return 0;
}
/*
Edge cases? n=1? a[i]<=0?
long vs int? 1LL? 64bits?
Re-read question. Is it as easy as it seems?
KEEP CORRECTING AND SUBMITTING!
*/


Measured memory_bytes: 3608
def segfunc(x,y):return x+y
ide_ele=0
class segtree():
  def __init__(self,init_val,segfunc=segfunc,ide_ele=ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]+=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num+1
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
st=segtree(list(map(int,input().split())))
ans=[]
for _ in range(q):
  x,y,z=map(int,input().split())
  if x:ans+=[st.query(y,z-1)]
  else:st.update(y,z)
print(*ans,sep='\n')

Measured memory_bytes: 158168
N = int(input())

X = []
Y = []

for i in range(N):
    x , y = map (int , input().split())
    X.append(x)
    Y.append(y)

total = 0

for i in range(0 , N-1):
    for j in range(i+1 , N):
        total += ((X[i]-X[j])**2 + (Y[i]-Y[j])**2)**(1/2)

average = 2 / N * total

print(average)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	String fileName = "prizes";

	public void solve() throws IOException {
		int a = nextInt();
		int b = nextInt();
		int c = nextInt();
		int x = nextInt() / 50;
		int ans = 0;
		for (int i = 0; i <= a; i++)
			for (int j = 0; j <= b; j++)
				for (int z = 0; z <= c; z++) {
					if (z + 2 * j + 10 * i == x)
						ans++;
				}
		out.println(ans);

	}

	public void run() {
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out, true);
			solve();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	BufferedReader br;
	StringTokenizer in;
	static PrintWriter out;

	public String nextToken() throws IOException {
		while (in == null || !in.hasMoreTokens()) {
			in = new StringTokenizer(br.readLine());
		}
		return in.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public static void main(String[] args) throws IOException {
		new Main().run();
	}

}

Measured memory_bytes: 21076
#include<bits/stdc++.h>
 
#define ll long long int
#define Y printf("YES\n")
#define N printf("NO\n")
#define pb push_back
#define tp make_tuple
#define srt(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define sc(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%lld%lld",&a,&b)
#define sc3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define pr(a) printf("%lld\n",a)
#define r0 return 0
#define pi acos(-1)
 
using namespace std;

int main()
{
	ll n,m,i,j,k,l,r,x,y,z,t;
	
	cin>>n;
	
	n=!n;
	
	cout<<n<<endl;
}

Measured memory_bytes: 3592
#include <stdio.h>
int main () {
  int n, i;
  long long r;
  scanf ("%d", &n);
  r = 1;
  for (i = 1; i < n+1; ++i) {
    r *= i;
    r = r % 1000000007;
  }
  printf ("%lld\n", r);
  return 0;
}

Measured memory_bytes: 1644
N = input()
a = input().split()
import numpy as np
a = np.array(a).astype(int).tolist()
count = 0
for aa in a:
    #n = np.log2(a)
    while(True):
        if aa % 2 == 0:
            aa = aa / 2
            count = count + 1
        else :
            break;
    
print(int(count))

Measured memory_bytes: 13620
# 1: starting from there, P1 wins (who starts)
# 0: P0 wins (who doesn't start)
# 
# 0 0 1 1 1 1 1
# 0 0 0 1 1
# 1 0 0 0 
# 1 1 0
# 1 1
# 1
# 1
# |X-Y| <= 1 : 0
# |X-Y| >  1 : 1
## X-Y: must change by 3
X, Y = map(int, input().split())
if abs(X-Y) > 1:
  print('Alice')
else:
  print('Brown')



Measured memory_bytes: 9056
function main(input) {
    var S = input.trim();

    var weather = [
        "Sunny",
        "Cloudy",
        "Rainy"
    ];

    var index = weather.indexOf(S);

    var tomorrowIndex = weather.length - 1 === index ? 0 : index + 1;
    console.log(weather[tomorrowIndex]);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int N, K;
  cin >> N >> K;
  int ans = 0;
  int x;
  for(int i = 0; i < N; i++){
    cin >> x;
    ans += 2 * min(x, K-x);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
const int N=105;
int H,W,i,j,f[N][N];
char c[N][N];
int main(){
	scanf("%d%d",&H,&W);
	for(i=1;i<=H;++i)scanf("%s",c[i]+1);
	f[1][1]=c[1][1]=='#';
	for(i=1;i<=H;++i)for(j=1;j<=W;++j)if(i>1 || j>1)
		f[i][j]=std::min(
			i>1?f[i-1][j]+(c[i][j]=='#' && c[i-1][j]=='.'):114514,
			j>1?f[i][j-1]+(c[i][j]=='#' && c[i][j-1]=='.'):114514);
	printf("%d\n",f[H][W]);
}

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

int main(){
int a, b, c, A, B, C;
cin>>a>>b>>c;
A=a, B=b, C=c;
if (a>b) a=B, b=A;
A=a, B=b, C=c;
if (b>c) b=C, c=B;
A=a, B=b, C=c;
if (a>b) a=B, b=A;
cout<<a<<" "<<b<<" "<<c<<endl;

return 0;
}




Measured memory_bytes: 3084
#include <iostream>

using namespace std;

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

    int ans = 0;
    for(int i = 1; i < n; i++){

        int cnt = 0;

        for(char j = 'a'; j <= 'z'; j++){

            bool right = false, left = false;

            for(int k = 0; k < i; k++){
                if(s[k] == j) right = true;
            }

            for(int l = i; l < n; l++){
                if(s[l] == j) left = true;
            }

            if(right && left){
                cnt++;
            }
        }

        ans = max(ans,cnt);

    }

    cout << ans << endl;
}


Measured memory_bytes: 888
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
	input! {
		cs: Chars,
	}

	let mut cmax = 0;
	let mut count = 0;
	for i in 0..3 {
		if cs[i] == 'R' {
			count += 1;
			cmax = max(cmax, count);
		}
		else {
			count = 0;
		}
	}
	println!("{}", cmax);
}



Measured memory_bytes: 2124
#include<bits/stdc++.h>
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;

#define int long long
#define cint cpp_int
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2
#define PI acos(-1.0)

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

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;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vvout(VVi &v){for(int i=0;i<(v).size();i++) vout(v[i]);}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int mypow(int x, int n, int m){if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}
int digit(int k,int i){string s = to_string(k);return s[s.size()-i]-'0';}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
Vi accum(Vi v){Vi ret((v).size());ret[0]=v[0];REP(i,1,(v).size()) ret[i]=ret[i-1]+v[i];return ret;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}



void solve(long long N, long long K, std::vector<long long> p){
    Vi sums=accum(p);
    int ans=sums[K-1];
//    cout<<ans<<endl;
    REP(i,K,N){
        chmax(ans,sums[i]-sums[i-K]);
//        cout<<sums[i]-sums[i-K]<<endl;
    }
    cout<<fixed<<setprecision(12)<<((double)ans+(double)K)/2.0<<endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
signed main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> p(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&p[i]);
    }
    solve(N, K, std::move(p));
    return 0;
}


Measured memory_bytes: 4992
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
{-# LANGUAGE BangPatterns    #-}
{-# LANGUAGE RecordWildCards #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM

main :: IO ()
main = do
    [n, q] <- map read.words <$> getLine :: IO [Int]
    queries <- U.unfoldrN q (readInt3.B.dropWhile isSpace) <$> B.getContents
    putStr.unlines.map show $ solve n queries

solve :: Int -> U.Vector (Int, Int, Int) -> [Int]
solve n queries = ($ []) $ runST $ do
    uf <- newUnionFind n
    U.foldM' `flip` id `flip` queries $ \ !acc (com,x,y) ->
        if com == 0
        then uniteM x y uf >> return acc
        else (acc.).(:).fromEnum <$> equivM x y uf

-------------------------------------------------------------------------------

readInt3 :: B.ByteString -> Maybe ((Int,Int,Int), B.ByteString)
readInt3 bs = Just ((x,y,z),bsz)
  where
    Just (x, bsx) = B.readInt bs
    Just (y, bsy) = B.readInt $ B.unsafeTail bsx
    Just (z, bsz) = B.readInt $ B.unsafeTail bsy

data UnionFind m = UF
    { parent :: UM.MVector m Int
    , rank   :: UM.MVector m Int
    }

nothing :: Int
nothing = -1
{-# INLINE nothing #-}

newUnionFind :: PrimMonad m => Int -> m (UnionFind (PrimState m))
newUnionFind n = UF `liftM` UM.replicate n nothing `ap` UM.replicate n 0
{-# INLINE newUnionFind #-}

findM :: PrimMonad m => Int -> UnionFind (PrimState m) -> m Int
findM x uf@UF{..} = do
    px <- UM.unsafeRead parent x
    if px == nothing
    then return x
    else do
        ppx <- findM px uf
        UM.unsafeWrite parent x ppx
        return ppx
{-# INLINE findM #-}

uniteM :: PrimMonad m => Int -> Int -> UnionFind (PrimState m) -> m ()
uniteM x y uf@UF{..} = do
    px <- findM x uf
    py <- findM y uf
    when (px /= py) $ do
        rx <- UM.unsafeRead rank px
        ry <- UM.unsafeRead rank py
        case compare rx ry of
            LT -> UM.unsafeWrite parent px py
            GT -> UM.unsafeWrite parent py px
            EQ -> do
                UM.unsafeWrite parent px py
                UM.unsafeWrite rank py (ry + 1)
{-# INLINE uniteM #-}

equivM :: PrimMonad m => Int -> Int -> UnionFind (PrimState m) -> m Bool
equivM x y uf = (==) `liftM` findM x uf `ap` findM y uf
{-# INLINE equivM #-}

Measured memory_bytes: 15416
/*
Arthor : Ender_zzm
E-mail zzm_ender_wiggin@outlook.com
Blog oi.ender-zzm.pro
*/
#include <bits/stdc++.h>
using namespace std;

template<class T>
inline void read(T &a) {
    register T x = 0, flag = 1;
    register char ch;
    while (!isdigit(ch = getchar())) if (ch == '-') flag = -1;
    while (x = x * 10 + (ch & 15), isdigit(ch = getchar()));
    a = x * flag;
}

template <class T>
inline void write(T x) {
    if (x < 0)
        putchar('-'), x = -x;
    if(x >= 10) write(x / 10); 
    putchar(x % 10 + '0');
}

template<class T> inline bool Chkmax(T& x, const T& y) { return x < y ? x = y, true : false; }
template<class T> inline bool Chkmin(T& x, const T& y) { return x > y ? x = y, true : false; }

#define For(i, a, b) for (int i = (a); i <= (b); i++) 
#define Rep(i, a, b) for (int i = (a); i >= (b); i--) 
#define For_edge(x) for (int i = head[x]; i; i = net[i])
#define mem0(a) memset(a, 0, sizeof a)

#define int long long
int n;
signed main() {
	cin >> n;	
	int ans = 0;
	For (i, 1, n) {
		if (i % 3 == 0 || i % 5 == 0) continue;
		ans += i;
	}
	cout << ans << endl;
}


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

#define INF (1 << 29)

using namespace std;

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

int main()
{
	int H, W, T; vector<vector<vector<bool> > > M;

	while (true)
	{
		cin >> W >> H;

		if (W == 0 && H == 0) { break; }

		M = vector<vector<vector<bool> > >(H, vector<vector<bool> >(W, vector<bool>(4, false)));

		for (int i = 0; i < W; i++)
		{
			M[0][i][0] = true;
		}

		for (int i = 0; i < H; i++)
		{
			M[i][W - 1][1] = true;
		}

		for (int i = 0; i < W; i++)
		{
			M[H - 1][i][2] = true;
		}
		
		for (int i = 0; i < H; i++)
		{
			M[i][0][3] = true;
		}

		for (int i = 0; i < 2 * H - 1; i++)
		{
			for (int j = 0; j < (i % 2 == 0 ? W - 1 : W); j++)
			{
				cin >> T;

				if (T == 1)
				{
					if (i % 2 == 0)
					{
						M[i / 2][j][1] = true;
						M[i / 2][j + 1][3] = true;
					}
					else
					{
						M[i / 2][j][2] = true;
						M[i / 2 + 1][j][0] = true;
					}
				}
			}
		}

		vector<vector<int> > dp(H, vector<int>(W, INF)); dp[0][0] = 1;

		queue<pair<int, int> > que; que.push(make_pair(0, 0));

		while (!que.empty())
		{
			pair<int, int> p1 = que.front(); que.pop();

			int x = p1.first;
			int y = p1.second;

			for (int dir = 0; dir < 4; dir++)
			{
				if (M[y][x][dir] == false)
				{
					if (dp[y + dy[dir]][x + dx[dir]] == INF)
					{
						dp[y + dy[dir]][x + dx[dir]] = dp[y][x] + 1;

						que.push(make_pair(x + dx[dir], y + dy[dir]));
					}
				}
			}
		}

		if (dp[H - 1][W - 1] == INF)
		{
			cout << 0 << endl;
		}
		else
		{
			cout << dp[H - 1][W - 1] << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 3248
#include<bits/stdc++.h>
using namespace std;
 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 
 
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define endl '\n'
#define debug cout << "Hold right there sparky.....\n";
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;
 
typedef long long int ll;
 
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ll mod =1e9+7;
const ll N =1e6+7;

int main()
{ 
  
   IOS
   string s;
   cin>>s;
   ll k;
   cin>>k;
   if(s.size()==1)
   {
    cout<<k/2<<endl;
    return 0;
   }
   set<char> se;
   for(auto x:s)
   {
    se.in(x);
   }
   if(se.size()==1)
   {
      cout<<((s.size())*k)/2;
      return 0;
   }

   ll ans=0;
   ll j=0;
   while(j<s.size())
   {  
    ll c=0;
    ll i=j;
      while(j<s.size()&&s[j]==s[i])
      {
        c++;
        j++;
      }
      
      //trace(c);
      ans+=(c/2);

   }
   if(k==1)
   {
    cout<<ans<<endl;
   }
   else
   {
      ll ans1=0;
   ll j=0;
   s=s+s;
   while(j<s.size())
   {  
    ll c=0;
    ll i=j;
      while(j<s.size()&&s[j]==s[i])
      {
        c++;
        j++;
      }
      
      //trace(c);
      ans1+=(c/2);

   }  
   
   //trace(ans2);
   ans1=(ans1-ans);
   //trace(ans);
   cout<<ans+(k-1)*ans1<<endl;
   }
   //cout<<k*ans<<endl;
   
}


Measured memory_bytes: 256
using System;
//using System.Collections.Generic;
//using System.Linq;
//using System.Text;
//using System.Threading.Tasks;
using static System.Console;

namespace testConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            var i = Array.ConvertAll(ReadLine().Split(), double.Parse);
            WriteLine(i[0]/i[1]);
        }
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a,b,c;
    cin >> a >> b >> c;

    cout << (a + b + c - max(a, max(b,c))) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n-1];
	int b[n+1]={0};
	for(int i=0;i<n-1;i++){
		cin>>a[i];
		b[a[i]]++;
	}
	for(int j=1;j<=n;j++){
		cout<<b[j]<<"\n";
	}
  return 0;}

Measured memory_bytes: 5124
d, g = [int(v) for v in input().split()]
p = []
c = []
sums = []
for i in range(d):
    tmp = [int(v) for v in input().split()]
    p.append(tmp[0])
    c.append(tmp[1])
    sums.append(tmp[0] * 100 * (i+1) + tmp[1])

ans = 1e9
for mask in range(1 << d):
    s = 0
    num = 0
    rest_max = -1
    for i in range(d):
        if (mask >> i & 1) == 1:
            s += sums[i]
            num += p[i]
        else:
            rest_max = i
    if s < g:
        s1 = 100 * (rest_max + 1)
        need = (g - s + s1 - 1) // s1
        if need >= p[rest_max]:
            continue
        num += need
    ans = min(ans, num)

print(ans)

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

int main() {
  int n,a[110],alice=0,bob=0;
  cin >> n;
  for(int i=0 ;i<n ;i++){
    cin >> a[i];
  }
  sort(a,a+n,greater<int>());
  for(int i=0 ;i<n ;i++){
    if(i%2==0){
      alice += a[i];
    }else{
      bob += a[i];
    }
  }
  cout << alice - bob << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include <iostream>
using namespace std;
#define  LL long long

const int maxn = 1e5+55;

LL a[maxn],b[maxn];
LL x[maxn],v[maxn];
LL sum[maxn];
int main()
{
	LL n,c;
	cin>>n>>c;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>v[i];

	for(LL i=1;i<=n;i++)
		a[i]=a[i-1]+v[i]-(x[i]-x[i-1]);
	x[n+1]=c;
	for(LL i=n;i>=1;i--)
		b[i]=b[i+1]+v[i]-(x[i+1]-x[i]);

	for(LL i=2;i<=n;i++)
		a[i]=max(a[i-1],a[i]);

	for(LL i=n-1;i>=1;i--)
		b[i]=max(b[i],b[i+1]);
	LL ans=0;
	for(LL i=1;i<=n;i++){//i=0即不折回
		ans=max(ans,-x[i]+a[i]+b[i+1]); //顺时针，再折回
		ans=max(ans,-(c-x[i])+b[i]+a[i-1]);//逆时针 再折回
		ans=max(ans,a[i]);//顺时针，不折回
		ans=max(ans,b[i]);//逆时针，不折回
	}
	cout<<ans<<endl;




}


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

void normalize(vi &v){
  map<int,int> id;
  int k = 0;
  rep(i,v.size()){
    if(v[i] != 0 && id.count(v[i])==0)id[v[i]] = ++k;
  }
  
  rep(i,v.size())v[i] = id[v[i]];
}

int special(string s){
  int n = s.size(), cnt = 0;
  rep(i,n){
    if(s[i] == '?')s[i] = '#';
    if(s[i] == '#')cnt++;
  }

  rep(i,n-1){
    if(s[i]=='.' && s[i+1]=='.')return -1;
  }

  for(int i=1;i<n-1;i++){
    if(s[i]=='.' && s[i-1]=='#' && s[i+1]=='#')return -1;
  }

  return cnt;
}

int main(){
  int h,w;
  cin >> h >> w;
  vector<string> c(h);
  rep(i,h)cin >> c[i];

  if(h==1){
    cout << special(c[0]) << endl;
    return 0;
  }
  if(w==1){
    string s;
    rep(i,h)s += c[i];
    cout << special(s) << endl;
    return 0;
  }
  
  map<vi,int> cur;
  cur[vi(w,0)] = 0;
  
  rep(i,h)rep(j,w){
    map<vi,int> nxt;
    int nh = i, nw = j+1;
    if(nw==w)nh++, nw=0;
    //cout << i << " " << j << endl;

    for(pair<vi,int> p : cur){
      vi s = p.first, ns = s;
      int num = p.second;
      /*
      for(int u : s)cout << u << " ";
      cout << endl;
      */

      if(c[i][j] == '?' || c[i][j] == '.'){
	if( i>0 && s[j]==0 )goto OUT_W;
	if( j>0 && s[j-1]==0 )goto OUT_W;

	int cnt = 0;
	rep(k,w){
	  if(s[k]==s[j])cnt++;
	}
	if(i>0 && cnt==1)goto OUT_W;
	
	ns[j] = 0;
	nxt[ns] = max(nxt[ns], num);
      }
    OUT_W:;
      
      if(c[i][j] == '?' || c[i][j] == '#'){
	if( i>0 && j>0 && s[j]!=0 && s[j-1]==s[j] )goto OUT_B;
	int nc = 0;
	rep(k,w)nc = max(nc,s[k]); nc++;
	if(i>0 && s[j]>0)nc = s[j];
	if(j>0 && s[j-1]>0)nc = s[j-1];

	if(i>0 && s[j]>0)nc = s[j];
	if(j>0 && s[j-1]>0)nc = s[j-1];
	ns[j] = nc;
	
	if(i>0 && s[j]>0 && j>0 && s[j-1]>0){
	  int tmp = s[j];
	  rep(k,w){
	    if(s[k] == tmp)ns[k] = nc;
	  }
	}
	
	normalize(ns);
	nxt[ns] = max(nxt[ns], num+1);	
      }
    OUT_B:;
    }
    cur = nxt;
  }
  
  int ans = -1;
  for(pair<vi,int> p : cur){
    bool f = true;
    for(int u : p.first){
      if(u>1)f = false;
    }
    if(f)ans = max(ans, p.second);
  }
  cout << ans << endl;
}

Measured memory_bytes: 2164
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    vector<long long> divisor;
    for(long long i = 1;i*i <= n;i++)
    {
        if(n%i == 0)
        {
            divisor.push_back(i);
            if(i*i != n)
            {
                divisor.push_back(n/i);
            }
        }
    }
    long long sol = 0ll;
    for(auto i:divisor)
    {
        if(i == 1)
        continue;
        if(n/i >= 1 and n/i <= i - 2)
        {
            sol += i - 1;
        }
    }
    cout << sol;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define MININF -1e18L
#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 ALL(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> intint;

int main(void)
{
    int a,b,c;
    cin >> a >> b >> c;
    cout << a * b / 2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (1 << 20);

template <class T>
struct fenwick
{
	int sz;
	T tr[MAXN];

	void init(int n)
	{
		sz = n + 1;
		memset(tr, 0, sizeof(tr));
	}

	T query(int idx)
	{
		T ans = 0;
		for(; idx >= 1; idx -= (idx & -idx))
			chkmax(ans, tr[idx]);
		return ans;
	}

	void update(int idx, T val)
	{
		if(idx <= 0) return;
		for(; idx <= sz; idx += (idx & -idx))
			chkmax(tr[idx], val);
	}
};

int n, a, b;

void read()
{
	cin >> n >> a >> b;
}

void solve()
{
	if(a + b - 1 > n)
	{
		cout << -1 << endl;
		return;
	}

	vector<int> answer;
	for(int x = 1; x <= a; x++) answer.push_back(x);

	vector<int> bg;
	int val = n;
	for(int i = 0; i < a; i++)
	{
		int cnt = (n - answer.size() - bg.size());
		chkmin(cnt, b - 1);	

		for(int j = cnt; j >= 1; j--)
		{
			bg.push_back(val - j + 1);
			if((int)bg.size() + (int)answer.size() == n)
				break;
		}

		if((int)answer.size() + (int)bg.size() == n) break;
		val -= (b - 1);
	}

	if((int)answer.size() + (int)bg.size() != n) 
	{
		cout << -1 << endl;
		return;
	}

	reverse(bg.begin(), bg.end());
	reverse(answer.begin(), answer.end());
	while(!answer.empty())
	{
		bg.push_back(answer.back());
		answer.pop_back();
	}

	answer = bg;
	for(int x: answer) cout << x << " ";
	cout << endl;
}

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

	read();
	solve();
	return 0;
}



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

void solve()
{
   int n, h, w;
   cin>>h>>w>>n; int cnt=0, i=1;
   while(true)
   {
     cnt++;
     if(i*max(w,h)>=n)
     {
         break;
     }
     i++;
   }
   cout<<cnt<<endl;
}
int main()
{
    int t;
    t=1;
    while(t--)
    {
        solve();

    }
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int k,n;
    cin>>k>>n;
    vector<int> a;
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        a.push_back(temp);
    }
    vector<int> ans;
    for(int i=1;i<n;i++){
        ans.push_back(a[i]-a[i-1]);
    }
    int first=a[0];
    int last=a[a.size()-1];
    int left=k-last+first;
    // cout<<first<<" "<<last<<" "<<left;
    ans.push_back(left);
    sort(ans.begin(),ans.end());
    ll sum=0;
    // cout<<ans.size()<<endl;
    for(int i=0;i<ans.size()-1;i++){
        sum+=ans[i];
        // cout<<ans[i]<<" ";
    }
    cout<<sum<<endl;

}

Measured memory_bytes: 5612
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;

int main() {
	string s;
	vector<pair<int,int>> v;
	cin>>s;

	// validate
	if(s[s.size()-1] == '1') {
		cout<<-1<<endl;
		return 0;
	}
	if(s[0] == '0') {
		cout<<-1<<endl;
		return 0;
	}
	for(int i = 0; i < s.size()-1; i++) {
		if(s[i] != s[s.size()-i-2]) {
			cout<<-1<<endl;
			return 0;
		}
	}

	int curr = 1, m = s.size()-1;
	for(int i = s.size()/2-1; i >= 0; i--) {
		int x = i+1;
		// cout<<x<<" "<<m<<" "<<curr<<endl;
		if(s[i] == '1') {
			// cout<<i<<endl;
			for(int j = 0; j < m - x; j++) {
				v.push_back({curr, curr+j+1});
			}
			v.push_back({curr, curr+m-x+1});
			curr = curr+m-x+1;
			m -= (m-x+1);
		}
	}

	for(auto it : v) {
		cout<<it.first<<" "<<it.second<<endl;
	}
	return 0;
}

Measured memory_bytes: 2292
#include<bits/stdc++.h>
using namespace std;
int L,len,cnt,tong[100];
char ch[100];
vector<char> Ans;
vector<char> merge(int l,int r)
{
	vector<char> ret,ls,rs;
	if(l==r){
		for(int i=1;i<=tong[l];i++) ret.push_back(ch[l]);
		return ret;
	}
	int mid=(l+r)>>1,l1,l2; char ans[130];
	ls=merge(l,mid); rs=merge(mid+1,r);
	l1=ls.size(); l2=rs.size();
	if(!l1||!l2) {
		for(int i=1;i<=l1;i++) ret.push_back(ls[i-1]);  
		for(int i=l1+1;i<=l1+l2;i++) ret.push_back(rs[i-l1-1]);
		return ret; 
	}
	if(l1<l2) swap(l1,l2),swap(ls,rs);
	int lst=1; char s[130];
	for(int i=1;i<=l1;i++) s[i]=ans[i]=ls[i-1];
	for(int i=0;i<l2;i++)
	{
		int now=L-l1;
		for(int k=lst;k<=l1+1;k++)
		{
			for(int l=1;l<=l1+1;l++)
				if(l==k){
					for(int r=l;r<=l1;r++) s[r+1]=ans[r];
					s[l]=rs[i]; break;
				}
				else s[l]=ans[l];
			int tmp; printf("? "); cnt++;
			for(int l=1;l<=l1+1;l++) printf("%c",s[l]); puts("");
			fflush(stdout);
			scanf("%d",&tmp); 
			if(tmp==now-1) {
				for(int l=1;l<=l1+1;l++) ans[l]=s[l];
				lst=k+1; l1++; break;
			}
		}
	}
	for(int i=1;i<=l1;i++) ret.push_back(s[i]);
	return ret;
}
int main()
{
	for(int i=1;i<=26;i++) ch[i]='a'+i-1;
	for(int i=1;i<=26;i++) ch[i+26]='A'+i-1;
	for(int i=0;i<=9;i++) ch[i+53]='0'+i;
	for(int i=1;i<=62;i++)
	{
		printf("? "); cnt++; 
		for(int j=1;j<=128;j++) printf("%c",ch[i]); puts("");
		fflush(stdout);
		scanf("%d",&tong[i]); tong[i]=128-tong[i]; L+=tong[i];
	}
	Ans=merge(1,62);// cerr<<cnt<<" ";
	printf("! "); for(int i=1;i<=L;i++) printf("%c",Ans[i-1]); puts("");
	fflush(stdout);
}

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

using namespace std;

const int MAX_W = 1e5 + 5, MAX_N = 105;
int weight[MAX_N], value[MAX_N];
long long maximum_value[MAX_N][MAX_W];

int main()
{
    int no_of_items, total_weight;
    cin >> no_of_items >> total_weight;

    for(int i = 1; i <= no_of_items; i++)
        cin >> weight[i] >> value[i];

    memset(maximum_value, 0, sizeof(maximum_value));

    for(int i = 1; i <= no_of_items; i++)
    {
        for(int j = 1; j <= total_weight; j++)
        {
            if(j < weight[i])
                maximum_value[i][j] = maximum_value[i - 1][j];
            else
                maximum_value[i][j] = max(maximum_value[i - 1][j], value[i] + maximum_value[i - 1][j - weight[i]]);
        }
    }

    cout << maximum_value[no_of_items][total_weight];
    return 0;
}


Measured memory_bytes: 82304
#include <string.h>

#include <algorithm>
#include <iostream>
#include <vector>

#define rep1(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define MOD 1000000007

using namespace std;
using ll = long long;

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

  ll part1 = 1, part2 = 1, part3 = 1;

  rep1(i, N) {
    part1 *= 9;
    part2 *= 8;
    part3 *= 10;

    part1 %= MOD;
    part2 %= MOD;
    part3 %= MOD;
  }

  part1 *= 2;
  part1 %= MOD;

  ll temp = part1 - part2;
  temp %= MOD;
  if (temp < 0) {
    temp += MOD;
  }

  ll ans = part3 - temp;
  ans %= MOD;
  if (ans < 0) {
    ans += MOD;
  }

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

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, n) for (int i = 1; i <= (int)(n); i++)
#define ll long long
int in() {int x; cin>>x; return x;}
ll lin() {ll x; cin>>x; return x;}
string sin() {string x;cin>>x;return x;}
using graph = vector<vector<int>>;
using graph2 = vector<vector<pair<int, int>>>;

bool ifprime(int x){
    if(x==1)return false;
    if(x==2)return true;
    if(x%2==0)return false;
    for(int i=2;i*i<=x;i++){if(x%i==0)return false;}
    return true;
}
ll mod(ll x, ll y){if(x>=0||x%y==0) return x%y;return y+x%y;} //mod including minus
ll dv0(ll x, ll y){if(x>=0||x%y==0)return x/y;return x/y-1;} //rnd down
ll dv1(ll x, ll y){if(x%y==0) return dv0(x,y);return dv0(x,y)+1;} //rnd up

//Start from Here
int main(){
    int K=in();
    ll sum=0;
    int m;
    rep2(i, K){
        rep2(j, K){
            rep2(k, K){
                m=gcd(i, j);
                sum+=gcd(m, k);
            }
        }
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
#define MOD 1000000007

int main() {
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	int *l = new int[q];
	int *r = new int[q];
	for (int i = 0; i < q; i++) {
		cin >> l[i] >> r[i];
	}
	int *sum = new int[n];
	int flag = 0;
	sum[0] = 0;
	
	for (int i = 0; i < n; i++) {
		if (s[i] == 'A') {
			flag = 1;
			if (i > 0)sum[i] = sum[i - 1];
		}
		else if (s[i] == 'C') {
			if (flag == 1) {
				sum[i] = sum[i - 1] + 1;
			}
			else if (i > 0) {
				sum[i] = sum[i - 1];
			}
			flag = 0;
		}
		else {
			flag = 0;
			if (i > 0)sum[i] = sum[i - 1];
		}
	}
	
	for (int i = 0; i < q; i++) {
		cout << (sum[r[i] - 1] - sum[l[i] - 1]) << endl;

	}



	return 0;
}


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

int main(){
  string str;
  cin >> str;
  int q;
  cin >> q;

  string command = "";
  int a, b;
  string p = "";
  for(int i=0;i<q;i++){
    cin >> command;
    if(command == "replace"){
      cin >> a >> b >> p;
      str = str.replace(a, b-a+1, p);
    } else if(command == "reverse"){
      cin >> a >> b;
      string sub_str = str.substr(a, b-a+1);
      string sub_str_reverse = "";
      for(int k=sub_str.size()-1;k>=0;k--){
        sub_str_reverse += sub_str[k];
      }
      str = str.replace(a, b-a+1, sub_str_reverse);
    } else if(command == "print"){
      cin >> a >> b;
      for(int j=a;j<b+1;j++){
        cout << str[j];
      }
      cout << endl;
    }
  }
}



Measured memory_bytes: 3232
#include<stdio.h>
#include<string.h>
#include<math.h>
#include <stdlib.h>
#include<ctype.h>
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main () {
	int K,N;
	scanf("%d %d",&K,&N);
	int A[N];
	for(int i=0; i<N ; i++ ) {
		scanf("%d",&A[i]);
	}
	qsort(A, N, sizeof(int), compare_int );
	
	int max = 0;
	
	for(int i=0; i<N-1 ; i++ ) {
		int sakoshun = A[i+1] - A[i];
		if (sakoshun > max) {
			max = sakoshun;
		}
	}
	int sakoda = A[0] + K - A[N-1];
	if(sakoda > max) {
		max = sakoda;
	}
	printf("%d",K-max);
	
	
	return 0;
}

Measured memory_bytes: 1276
#include<stdio.h>
#include<iostream>
#include<list>
#include<map>
#include<math.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<iomanip>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug" << x << endl;
using namespace std;

int main(){
    int fx[200000], n;
    cin >> n;
    rep(i, n){
        cin >> fx[i];
    }

    int maxv = -2000000000, minv = fx[0];
    range(i, 1, n){
        maxv = max(maxv, fx[i] - minv);
        minv = min(minv, fx[i]);
    }
    cout << maxv << endl;

    return 0;
}

Measured memory_bytes: 1940
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

struct Edge{
    int u, v, w;
};

int main(){

    int L;
    cin >> L;

    vector<Edge> E;

    int digit = 0;
    int tempL = L;
    while(tempL != 0){
        digit++;
        tempL /= 2;
    }
    int len = digit - 1;

    int temp = (1 << (len - 1));
    for(int i = 0; i < len; i++){
        Edge e;
        e.u = i + 1;
        e.v = i + 2;
        e.w = temp;
        E.emplace_back(e);
        temp /= 2;
        e.w = 0;
        E.emplace_back(e);
    }

    int bit = (1 << (len - 1));
    tempL = L - ((1 << len));
    int sum = (1 << len);
    for(int i = len - 1; i >= 0 ; i--){
        if(bit & tempL){
            Edge e;
            e.u = 1;
            e.v = (len + 1 - i);
            e.w = sum;
            E.emplace_back(e);
            sum += (1 << i);
        }

        bit = (bit >> 1);
    }

    cout << len + 1 << " " << (int)E.size() << endl;
    for(auto e: E){
        cout << e.u << " " << e.v << " " << e.w << endl;
    }

    return 0;
}

Measured memory_bytes: 256
# coding: utf-8

def fact(n, m):
    ans = 1
    for i in range(n-m+1, n+1):
        ans *= i
    return ans

if __name__ == "__main__":
    N = int(input())
    s = []
    c = {}
    for i in range(N):
        a = "".join(sorted(input()))
        s.append(a)
        try:
            c[a] += 1
        except KeyError:
            c[a] = 1
    
    ans = 0
    for k,v in c.items():
        ans += fact(v,2)/2
    
    print(int(ans))

Measured memory_bytes: 18568
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  string n;
  cin>>n;
  if((n[0]==n[1])&&(n[1]==n[2])){
    cout<<"Yes"<<endl;
  }else if((n[1]==n[2])&&(n[2]==n[3])){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
use proconio::input;
use proconio::marker::Chars;
#[allow(unused_mut)]
fn main() {
    input! {
        _n: usize,
        s: Chars,
    }
    let s: Vec<char> = s;
    let mut res = 1;
    let mut before = s[0];
    for i in s.iter() {
        if before != *i {
            res += 1;
            before = *i;
        }
    }
    println!("{}", res);
}


Measured memory_bytes: 2452
N = int(input())


L = [ [0]*10 for i in range(10) ]

# 数字を文字にして、[0]と[-1]を使うアイデアが参考になる
for i in range(1,N+1):
    n = str(i)
    head = int(n[0])
    tail = int(n[-1])
    L[head][tail] += 1

ans = 0

for j in range(10):
    for k in range(10):
        ans += L[j][k] * L[k][j]

print(ans)

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

using i64 = int64_t;

int main(){
    int n, m;
    while(cin >> n >> m, n > 0){
        vector<pair<string, int>> v;
        for(int i=0;i<n;++i){
            string s;
            int money;
            cin >> s >> money;
            v.emplace_back(s, money);
        }
        int ans = 0;
        for(int i=0;i<m;++i){
            string b;
            cin >> b;
            for(auto e: v){
                bool flag = true;
                for(int j=0;j<8;++j){
                    if(e.first[j] != '*' && e.first[j] != b[j]){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    ans += e.second;
                    break;
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3176
#include <iostream>

using namespace std;

using ll = long long;

int main() {
  ll a, b;
  cin >> a >> b;
  if (a <= 0 && 0 <= b) {
    cout << "Zero" << endl;
    return 0;
  }


  
  if (a > 0 || (b - a) % 2 == 1) {
    cout << "Positive" << endl;
  } else {
    cout << "Negative" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
N,x = map(int,input().split())
if x == 1 or x == 2*N-1:
    print('No')
else:
    print('Yes')
    if x == N:
        A = list(range(1,2*N))
    elif N < x < 2*N-1:
        A = list(range(1+x-N,2*N)) + list(range(1,1+x-N))
    else:
        A = list(range(2*N-(N-x),2*N)) + list(range(1,2*N-(N-x)))
    print('\n'.join(map(str,A)))

Measured memory_bytes: 25044