akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
typedef long long ll;

int main(){
  int n;
  cin>>n;
  ll ans=0;
  vector<int> d(100002);
  vector<int> a(n);
  rep(i,n){
    cin>>a[i];
    d[a[i]]++;
    ans+=a[i];
  }
  int q;
  cin>>q;
  while(q--){
    int b,c;
    cin>>b>>c;   
    ans=ans+(c-b)*d[b];
    d[c]+=d[b];
    d[b]=0;
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
/*
 execution in cmd of windows: g++ p1.cpp -op1
  
  
  p1
 
 */
typedef double dd;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define nl <<"\n"
#define con continue
#define br break
#define vll vector<ll>
#define vpll vector<pair<ll,ll> >
ll mx=INT_MAX;
ll mi=INT_MIN;
#define mem0(a)         memset(a,0,sizeof(a))
#define mem1(a)         memset(a,-1,sizeof(a))
#define all(v) v.begin(), v.end()
#define fsort(v) sort(all(v))  
#define rsort(v) sort(v.rbegin(),v.rend())
#define rev(v) reverse(all(v))
#define maxc(v) max_element(all(v))
#define minc(v) min_element(all(v))
#define sumv(v,x) accumulate(v.begin(),v.end(),x);
const ll mod = 1000000007;
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
#define io { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define cer cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
#define cs ll t;cin>>t;while(t--)
#define cs1 ll t;t=1;while(t--)


int main()
{
   
        io;
        //////////////////////////////////
        cs1{
             ll i,j,k,l,s=0,p=INT_MAX,n,m,q=0,e;
             string st,ss;
             cin>>st>>ss;
             for(i=0;i<st.size()-ss.size()+1;i++){
                 s=0;
                 for(j=0;j<ss.size();j++){
                     if(ss[j]!=st[j+i]) s++;
                 }
                 p=min(p,s);
             }
             cout<< p nl;

        }
        //////////////////////////////////
 
}

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

using namespace std;

typedef long long ll;
int n;
const int maxN = 1e5 + 10;
int a[maxN];
int main() {
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    int mn = n + 1;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    if (mx - mn > 1) {
        cout << "No";
        return 0;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == mn) cnt++;
    }
    //uniq = cnt
    int x = 0;
    int not_uniq = n - cnt;
    if (not_uniq == 0) {
        if (n - 1 == mn) {
            cout << "Yes\n";
            return 0;
        }
        if (mn <= n / 2) {
            cout << "Yes\n";
            return 0;
        }
        cout << "No";
        return 0;
    }
    else {
        int clrs = mx - cnt;
        if (clrs < 0 || (clrs == 0 && not_uniq > 0)) {
            cout << "No";
            return 0;
        }
        if (not_uniq >= clrs * 2) {
            cout << "Yes\n";
        }
        else {
            cout << "No";
        }
    }
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <functional>

using namespace std;

typedef long long int ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
	int N;
	cin >> N;
	ll ans = 0;
	REP(i, N)
	{
		ll a;
		cin >> a;
		ans += (a - 1);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<assert.h>
#define INT_MAX 2147483647
typedef long long ll;
using namespace std;
vector<vector<int>>graph;
vector<int>dp;
vector<bool>visited;
vector<int>indegree;
int dfs(int node){
	visited[node] = true;
	int ans = 0;
	for (int i = 0; i < graph[node].size(); i++){
		if (!visited[graph[node][i]]){
			ans = max(ans, 1 + dfs(graph[node][i]));
		}
		else{
			ans = max(ans, 1+dp[graph[node][i]]);
		}
	}
	return dp[node] = ans;
}
int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("output1.txt", "w",stdout);
	int n, m,x,y;
	cin >> n >> m;
	dp.resize(n + 1,-1);
	graph.resize(n + 1);
	visited.resize(n + 1,false);
	indegree.resize(n + 1,0);
	for (int i = 0; i < m; i++){
		cin >> x >> y;
		indegree[y]++;
		graph[x].push_back(y);
	}
	int answer = 0;
	for (int i = 1; i <= n; i++){
		if (indegree[i] == 0){
			answer = max(answer,dfs(i));
		}
	}
	cout << answer << endl;
	return 0;
}

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

using namespace std;
string s;
int a,b,ans;
int main()
{
	cin>>a>>b;
	cin>>s;
    for(int i=0;i<s.size();i++)
	{
	   if(i!=a)
	   {
	   	  if(s[i]>='0' && s[i]<='9') ans++;
	   }
	}
	if(ans==a+b && s[a]=='-') cout<<"Yes";
	else cout<<"No";
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(int argc,char *args[]){
    int a,c,ans;
    char b;
    while(1){
        scanf("%d %c %d",&a,&b,&c);
        if (b == '?') break;
        else if(b == '+') ans = a+c;
        else if(b == '-') ans = a-c;
        else if(b == '*') ans = a*c;
        else if(b == '/') ans = a/c;
        printf("%d\n",ans);
    }
    return 0;
}



Measured memory_bytes: 2104
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
const int INF = 1e9;

int main() {
  char c;
  cin >> c;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    cout << "vowel" << endl;
  } else {
    cout << "consonant" << endl;
  }
}


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

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

    if (s == "Sunny") cout << "Cloudy" << endl;
    if (s == "Cloudy") cout << "Rainy" << endl;
    if (s == "Rainy") cout << "Sunny" << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		var B = (int[]) A.Clone();
		Array.Sort(B);
		HashSet<int> H = new HashSet<int>();
		for(int i=0;i<N;i+=2) H.Add(B[i]);
		
		int cnt = 0;
		for(int i=0;i<N;i+=2) if(!H.Contains(A[i])) cnt++;
		
		Console.WriteLine(cnt);
		
		
	}
	int N;
	int[] A;
	public Sol(){
		N = ri();
		A = new int[N];
		for(int i=0;i<N;i++) A[i] =ri();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


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

using namespace std;

#define ff first
#define ss second
#define pb push_back

using ll = long long;
using ii = pair<int ,int>;

const int N = 5e5 + 5;

int v[N];
int main(){
	char s[N];
	scanf("%s", s);
	int n = (int)strlen(s);
	for(int i = 0; i < n; i++){
		if(s[i] == '<'){
			v[i+1] = v[i]+1;
		}
	}
	for(int i = n-1; i >= 0; i--){
		if(s[i] == '>'){
			v[i] = max(v[i], v[i+1]+1);
		}
	}
	n++;
	ll ans = 0;
	for(int i = 0; i < n; i++){
		ans += v[i];
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 2688
def Eratosthenes(n):
    li = [i for i in range(2,n+1)]
    judge = [True for i in range(n+1)]
    ans = []
 
    for i in range(2,n+1):
        if judge[i] == True:
            for j in range(i*2,n+1,i):
                judge[j] = False
            ans.append(i)
    return ans
 
x = int(input())
l = Eratosthenes(10 ** 6)
for i in l:
    if i >= x:
        print(i)
        exit()

Measured memory_bytes: 54196
#include <bits/stdc++.h>
#define P pair<int,int>
#define All(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
typedef long long ll;
using namespace std;
const int INF = 1e9, MOD = 1e9 + 7;
const ll LINF = 1e18;
int main() {
	int a, b, c, x, cnt = 0;
	cin >> a >> b >> c >> x;
	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			for (int k = 0; k <= c; k++) {
				if (500 * i + 100 * j + 50 * k == x) {
					cnt++;
				}
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long a,b,c,x,i,j,k,ans;
	    cin>>a>>b>>c>>x;
	      ans=0;
	    for(i=0;i<=a;i++)
	     for(j=0;j<=b;j++)
	      for(k=0;k<=c;k++)
	       if((i*500+j*100+k*50)==x)ans++;
	          cout<<ans;
	         return 0;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>

#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

#include <stdexcept>

using namespace std;

// type alias
using ll = long long;
using ull = unsigned long long;
using comp = complex<double>;

const ll MOD = 1000000007LL;
const double PI = 3.14159265358979323846;

//conversion
//------------------------------------------
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class t> inline string tostring(t x) { ostringstream sout; sout << x; return sout.str(); }

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

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl
#define DEBUG(x) cerr << #x << " = " << (x) << " (l" << __line__ << ")" << " " << __file__ << endl

int solve() {
	ll h1, m1, h2, m2, k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;

	ll start = h1 * 60 + m1;
	ll end = h2 * 60 + m2;

	cout << end - start - k << endl;

	return 0;
}

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

	solve();

	return 0;
}


Measured memory_bytes: 3652
#define z 1000000
main(){int a[z]={},b[z]={},n,i,x=0,c;for(i=2;i<z;i++)a[i]=i;for(i=0;i<z;i++)if(a[i]!=0){b[x++]=i;for(c=i;c<z;c+=i)a[c]=0;}while(scanf("%d",&n)!=-1){c=0;while(b[c]<=n && b[c]!=0){c++;}printf("%d\n",c);}exit(0);}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  int dp[n];
  dp[0]=0;
  dp[1]=abs(a[1]-a[0]);
  for(int i=2;i<n;i++)
  {
    dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
  }
  cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 4404
import numpy as np

s = input().split()
N=int(s[0])
s = input().split()
a = [int(i) for i in s]
s = input().split()
b=[int(i) for i in s]
c=0
for i in range(N):
    if a[i]-b[i]<0:
        c = c+a[i]+min(a[i+1], b[i]-a[i])
        a[i+1]=a[i+1]+a[i]-b[i]
        if a[i+1]<0:
            a[i+1]=0
    else:
        c=c+b[i]
print(c)

Measured memory_bytes: 32752
#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;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

const int MAXN = 100005;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	string s; cin>>s;
	int ans=0;
	int cnt=1;
	forn(i,1,n){
		if(s[i]==s[i-1]);
		else {ans+=cnt; cnt=1; }
	}
	ans+=cnt;
	cout<<ans<<'\n';
	
	return 0;
}


Measured memory_bytes: 3764
#include <stdio.h>

int main(void){
  int second;
  int h,m,s;

  scanf("%d\n", &second);

  if(0 <= second && second < 86400){
     h = (second / 3600);
     m = (second % 3600) / 60;
     s = (second % 3600) % 60;
     printf("%d:%d:%d\n", h,m,s);

  }

  return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
struct E{int u,v,c;};
int l,p=1,mx,n,s1;
vector<E> ans;
int main(){
	scanf("%d",&l);l--;
	int i;
	for(i=1;mx+p<=l;++i){
		ans.push_back({i,i+1,p});
		ans.push_back({i,i+1,0});
		mx+=p,p*=2;
	}
	n=i--,p/=2,s1=mx-p;
	while(mx<l){
		if(mx+s1+1<=l)ans.push_back({i,n,mx+1}),mx+=s1+1;
		p/=2,s1-=p,i--;
	}
	printf("%d %d\n",n,ans.size());
	for(int i=0;i<ans.size();++i)printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].c);
} 

Measured memory_bytes: 256
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for comb in combinations(range(1, N), K - 1):
        included = [False] * N
        for i in comb:
            included[i] = True

        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if included[i]:
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<61;
const ll mod=1e9+7;

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;
}

int main(){
  int i,j;
  int n,m;
  cin>>n>>m;
  VI v(n+1,-1);
  for(i=0;i<m;i++){
    int s,c;
    cin>>s>>c;
    if(v[s]>=0&&v[s]!=c){
      cout<<-1<<endl;
      return 0;
    }
    v[s]=c;
  }
  if(n==1){
    if(v[1]<=0){
      cout<<0<<endl;
      return 0;
    }
  }
  if(v[1]==0) {
    cout<<-1<<endl;
    return 0;
  }
  for(i=1;i<=n;i++){
    if(i==1) cout<<max(1ll,v[i]);
    else cout<<max(0ll,v[i]);
  }
  cout<<endl;

}

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

using namespace std;
typedef long long ll;
#define INF 1e9

double calcarea(int a, int b) {
  return (double)(a + b)/8.0;
}

int main() {
  int n;
  cin >> n;
  vector<int> t(n), v(n);

  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> t[i];
    sum += t[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }

  vector<int> limitSpeed(sum * 2 +1, INF);
  int now = 0;
  for (int i = 0; i < n; i++) {
    for (int j = now; j <= t[i]*2 + now; j++) {
      limitSpeed[j] = min(limitSpeed[j], v[i] * 2);
    }
    now += t[i] * 2;
  }

  limitSpeed[0] = 0;
  for (int i = 0; i < sum * 2; i++) {
    limitSpeed[i + 1] = min(limitSpeed[i + 1], limitSpeed[i] + 1);
  }
  limitSpeed[sum*2] = 0;
  for (int i = sum * 2; i >= 0; i--) {
    limitSpeed[i - 1] = min(limitSpeed[i - 1], limitSpeed[i] + 1);
  }

  double ans = 0.0;
  for (int i = 0; i < sum * 2; i++) {
    ans += calcarea(limitSpeed[i], limitSpeed[i + 1]);
  }
  cout << fixed << setprecision(12) << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
  int n,a[100],i,j,k;
  string s;
  cin>>s;
 n=s.size();
 // cout<<s[0]-'a'<<endl;
 for(i=0;i<26;i++){a[i]=0;}
  for(i=0;i<n;i++){a[s[i]-'a']++;}
  
  for(i=0;i<26;i++){if(a[i]%2!=0){cout<<"No";return 0;}}
  cout<<"Yes";
  
  return 0;
}

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

const int N = 300005;

int n, k, a[N], l;

void prev() {
	if (a[l] == 1) --l;
	else --a[l], std::fill(a + l + 1, a + n + 1, k), l = n;
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> k >> n;
	if (k & 1) {
		l = n; for (int i = 1; i <= n; ++i) a[i] = k + 1 >> 1;
		for (int t = n >> 1; t; --t) prev();
		for (int i = 1; i <= l; ++i) std::cout << a[i] << ' ';
		std::cout << '\n';
	} else {
		std::cout << k / 2;
		while (--n) std::cout << ' ' << k;
		std::cout << '\n';
	}
	return 0;
}

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


void input(); template<typename First,typename... Rest> void input(First&,Rest&...);
void inputVector(); template<typename First,typename... Rest>  void inputVector(std::vector<First>&,Rest&...);
#define loop(n) for(int i = 0;i < (int)(n);++i)
#define rep(i,n) for(int i = 0;i < (int)(n);++i)
#define all(vec) (vec).begin(),(vec).end()
#define sort(vec) std::sort(all(vec))
#define rev(vec) std::reverse(all(vec))

void calculate(){

}

int main(int,char**){
    int N;
    input(N);
    for(unsigned int i = N;1 <= i;--i)
    {
        if((i & (i - 1)) == 0)
        {
            std::cout << i << std::endl;
            return 0;
        }
    }
}


void input(){return;}
template<typename First,typename... Rest>
void input(First &first,Rest&... rest){
    std::cin >> first;
    input(rest...);
}

void inputVector(){return;}
template<typename First,typename... Rest> 
void inputVector(std::vector<First> &first,Rest&... rest){
    int N = first.size();
    for(int i = 0;i < N;i++){
        std::cin >> first[i];
    }
    inputVector(rest...);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i = 0; i<n; i++)
using namespace std;
int main() {
  int n, k;
  string s;
  cin >> n >> k >> s;
  s.at(k-1)=s.at(k-1)-'A'+'a';
  cout << s << endl;
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
monster=[]
for i in range(n):
    x,h=map(int,input().split())
    monster.append((x,h))
monster.sort()
x_list=[]
h_list=[]
for i in monster:
    x_list.append(i[0])
    h_list.append(i[1])
ans=0
import bisect
damage=[0]
for i in range(n):
    p=bisect.bisect_left(x_list,x_list[i]-2*d)
    D=damage[i]-damage[p]
    if h_list[i]<=D:
        damage.append(damage[-1])
        continue
    r=h_list[i]-D
    c=(r+a-1)//a
    ans+=c
    damage.append(damage[-1]+a*c)
print(ans)
    
    


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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO ?????????????????????????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			String[] tmpArray = br.readLine().split(" ");

			int n = Integer.parseInt(tmpArray[0]);
			int k = Integer.parseInt(tmpArray[1]);
			
			if(n == 0 && k == 0){
				break;
			}
			
			int[] input = new int[n];
			for(int i = 0; i < n; i++){
				input[i] = Integer.parseInt(br.readLine());
			}
			
			int sum = 0;
			int max = Integer.MIN_VALUE;
			//????????????????????????????¨???????????????????
			for(int i = 0; i < k; i ++){
				sum += input[i];
			}
			max = sum;
			//System.out.println("sum "+sum);
			
			for(int i = 1; i <= n - k; i++){
				sum += input[i + k - 1];
				sum -= input[i - 1];
				
				//System.out.println("sum "+sum);
				if(sum > max){
					max = sum;
				}
			}
			
			System.out.println(max);
			
		}
	}

}

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


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

    long long i,j,k,l,m,n,o,p;
    while(cin>>p)
    {
        char x[1000009]= {0};
        n=0;
        m=0;
        for(i=0; i<p; i++)
        {
            cin>>j;
            if(j>m)
                m=j;
            x[j]++;
        }
        char y[m+1]= {0};

        for(i=1; i<=m; i++)
        {
            if(x[i]>0)
            {
                for(k=i*2; k<=m; k+=i)
                    y[k]++;
            }
        }

        j=0;
        for(i=1; i<=m; i++)
        {
            if(x[i]==1&&y[i]==0)
                j++;
        }

        cout<<j<<endl;

    }


    return 0;


}


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

const double pi = acos(-1);
int n, m;
const int maxn = 1e4 + 5;
int a[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int sum = 0;
    for(int i = 1;i <= m;i++){
        cin >> a[i];
        sum += a[i];
    }
    if(sum <= n){
        cout << n - sum << endl;
    }else{
        cout << -1 << endl;
    }
    return 0;
}


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

using namespace std;

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

	vector<int> v(10000001, 1);
	for (int i = 2; i < 10000001; ++i) {
		int a = i;
		while (a <= 10000000) {
			++v[a];
			a += i;
		}
	}

	long long ret = 0;
	for (int i = 1; i <= n; ++i) {
		ret += (long long)i * (long long)v[i];
	}
	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 42308
from collections import*
import functools
import sys
input=sys.stdin.readline
@functools.lru_cache(maxsize=None)
def Knapsack(N,W):
    for i in range(N):
        w,v=map(int,input().split())
        for k,b in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],b+v)
    return max(d.values())
N,W=map(int,input().split())   #pypyで実行！
d=defaultdict(int)
d[0]=0
print(Knapsack(N,W))


Measured memory_bytes: 4124
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<cmath>
#include<set>
#include<random>
#include<map>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 11451419198109130;
typedef pair<int, int> P;
typedef pair<int,P> PP;
struct edge { int to, cor; };
vector<int>G[114514];
int n, k;
int a[200005];
int rwa[200005];
int bit[200005];
int sum(int i) {
	int s = 0;
	while (i) {
		s += bit[i];
		i -= i&-i;
	}
	return s;
}
void add(int i, int x) {
	while (i <= n) {
		bit[i] += x;
		i += i&-i;
	}
}
int solve() {
	int ans = 0;
	rep(j, n) {
		ans += sum(rwa[j]);
		add(rwa[j], 1);
	}
	return ans;
}
map<int, int>M1, M2;
signed main() {
	cin >> n >> k;
	rep(i, n) {
		cin >> a[i];
		rwa[i + 1] = a[i];
	}
	rep(i, n)rwa[i + 1] += rwa[i];
	rep(i, n + 1)rwa[i] -= i*k;
	rep(i, n + 1) {
		M1[rwa[i]]++;
	}
	int now = 0;
	for (auto itr = M1.begin(); itr != M1.end(); itr++) {
		M2[itr->first] = now;
		now++;
	}
	rep(i, n + 1) {
		rwa[i] = M2[rwa[i]]+1;
	}
	n++;
	cout << solve() << endl;
}

Measured memory_bytes: 33152
#include<bits/stdc++.h>
using namespace std;
int n,k,a[501],sumn,ans;
bool Check(int x){
	int h[501],sum=0,zk=0;
	for(int i=1;i<=n;i++){
		h[i]=a[i]%x;
		sum+=h[i];
	}
	sort(h+1,h+n+1);
	int m=sum/x;
	for(int i=1;i<=n-m;i++){
		zk+=h[i];
		if(zk>k)return 0;
	}
	return 1;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sumn+=a[i];
	}
	for(int i=1;i*i<=sumn;i++)if(sumn%i==0){
		if(Check(sumn/i)){printf("%d",sumn/i);return 0;}
		if(Check(i))ans=i;
	}
	printf("%d",ans);
}

Measured memory_bytes: 256
#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;  
#define ordered_set tree<ll, null_type , less<ll> , rb_tree_tag , tree_order_statistics_node_update> 
#define ll long long
#define ull unsigned long long
#define pb push_back
#define inf 1e18
#define mk make_pair
#define ld long double
#define mod 1000000007
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test ll t; cin>>t; while(t--)
#define setbits __builtin_popcount
#define endl '\n'
#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i));}
sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int main()
{
    fastIO;
    ll a,val,val1;
    ld b;
    cin>>a>>b;
    val=round(b*100);
    val1=(a*val)/100;
    cout<<val1<<endl;
}

Measured memory_bytes: 3756
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include<vector>
#include<cstring>
#include<set>
#include <cstdio>
#include<queue>
#include<map>
#define WHITE 0
#define GRAY  1
#define BLACK 2
#define endl '\n'
#define forup(i,a,n) for( int i =a; i < n; i++)
#define llforup(i,a,n) for( ll i =a; i < n; i++)
#define fordown(i,a,n) for( int i =a; i >= n; i--)
#define fornot(i,a,n) for( int i=a;!n;i++)
#define mod  (ll)(1e9+7)
#define ifempty(a)  if(!a)
using namespace std;
typedef long long ll;
inline int readnum()
{
	int p, data = 0; char ch = 0;
	while ((ch != ' - ') && ch < '0' || ch>'9') ch = getchar();//相当于正则表达式的搜索，跳过不需要的字符
	if (ch == '- ')p = -1, ch = getchar();
	else p = 1;
	while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = getchar();//搜索需要的字符
	return data * p;
}
inline int ReadPossitive()
{
	char ch; int data = 0;
	ch = getchar();
	while (ch == ' ' || ch == '\n')ch = getchar();
	while (ch != ' ' && ch != '\n' && ch != EOF)
	{
		data = data * 10 + ch - '0';
		ch = getchar();
	}
	return data;
}
//E-mail 374656045@qq.com
class solve {
private:ll m, n;ll  ans;
public:
	solve()
	{
		 m= ReadPossitive();n = ReadPossitive();
		 ans = qpower(m,n);
		printf("%lld\n", ans);
	}
	ll qpower(ll x,ll n)//原理是恒等变换，底数翻倍，指数减半，使得指数呈等比数列递减至0.较朴素算法累乘效率高得多
	{
		ll temp=1;
		while (n > 0)
		{//注意两个int整数容易导致整数溢出,将x,n都改为ll的方案比强制转型更保险
			if (n & 1)temp = x*temp%mod;//如果n是奇数要特殊处理，先指数减一，结果乘以x保持恒等，剩下的部分再继续恒等折半操作
			x = x * x%mod;//不要忘记步步取模
			n >>= 1;//相当于除以2，由于这种除法同样是精度缺省的向下取整操作，所以奇数特殊处理的先减一再折半可以与偶数的处理方式合并成同一条式子
		}
		return temp;
	}
	
};
int main(void)
{
	ios_base::sync_with_stdio(0); cin.tie(0);//慎用，cin和scanf混用会导致非MSC++WA
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	solve solution;
#ifdef DEBUG
	fclose(stdin);//关闭文件 
	fclose(stdout);//关闭文件 
#endif
	return 0;

}




Measured memory_bytes: 3248
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<(int)N;i++)
int N,z=0;
vector<int> witness(15,0);
vector<vector<int>> x(15,vector<int>(15,0)),y(15,vector<int>(15,-1));
void judge(int a)
{
  int count=0;
  rep(i,N){if((a/(int)pow(2,i))%2){count++;rep(j,witness.at(i))if((a/(int)pow(2,x.at(i).at(j))%2)!=y.at(i).at(j))return;}}
  z=max(count,z);
}
int main()
{
  cin>>N;
  rep(i,N){cin>>witness.at(i);rep(j,witness.at(i))cin>>x.at(i).at(j)>>y.at(i).at(j),x.at(i).at(j)--;}
  rep(i,pow(2,N)-1)judge(i+1);
  return cout<<z<<endl,0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#define rep(i, n) for(int i=0 ; i<n; ++i)
using namespace std;

int main(){
    long N, K, X, Y;
    cin >> N;
    cin >> K;
    cin >> X;
    cin >> Y;
    long sum=0;
    rep(i, N){
        if(i<K)sum+=X;
        else sum+=Y;
    }
    cout<<sum<<endl;
}

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}


int main(){
  int N; cin >> N;
  for (int i = 0; i < N; i++){
    char C; cin >> C;
    if (C == 'Y'){
      cout << "Four" << endl;
      return 0;
    }
  }
  cout << "Three" << endl;

  return 0;
}


Measured memory_bytes: 3640
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    a,b=inpm()
    c,d=inpm()
    if a==c:
        print(0)
    else:
        print(1)

if __name__ == "__main__":
    main()

Measured memory_bytes: 40716
#include <iostream>
#include <string>
using namespace std;
int main(){
  int H, W;
  cin >> H >> W;
  string a[60];
  for(int i = 1; i <= H ; ++i){
    cin >> a[i];
  }
  const int dx[4] = {1, 0, -1, 0};
  const int dy[4] = {0, -1, 0, 1};

 bool can = true;
 for(int i = 1; i <= H; ++i){
   for(int j = 0; j < W; ++j){
     if(a[i][j] != '#') continue;
     bool can2 = false;
     for(int d = 0; d < 4; ++d){
       if(a[i+dx[d]][j+dy[d]] == '#') can2 = true;
     }
     if(can2 == false){
       can = false;
       break;
     }
   }
 }
 if(can) cout << "Yes" << endl;
 else cout << "No" << endl; 
}

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

#ifdef WIN32
    #define lld "%I64d"
#else
    #define lld "%lld"
#endif

#define mp make_pair
#define pb push_back
#define put(x) { cout << #x << " = "; cout << (x) << endl; }

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef double db;

const int M = 1e6 + 15;
const int Q = 1e9 + 7;

int scntA[M], scntB[M], tcntA[M], tcntB[M];
int main() {
    srand(time(NULL));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	string s, t;
	cin >> s >> t;
	for (int i = 1; i <= (int)s.size(); i++) {
		scntA[i] = scntA[i - 1] + (s[i - 1] == 'A');
		scntB[i] = scntB[i - 1] + (s[i - 1] == 'B');
	}

	for (int i = 1; i <= (int)t.size(); i++) {
		tcntA[i] = tcntA[i - 1] + (t[i - 1] == 'A');
		tcntB[i] = tcntB[i - 1] + (t[i - 1] == 'B');
	}

	int q;
	cin >> q;
	while (q--) {
		int l1, r1, l2, r2;
		cin >> l1 >> r1 >> l2 >> r2;
		l1--, l2--;
		int sc = (scntB[r1] - scntB[l1]) - (scntA[r1] - scntA[l1]);
		int tc = (tcntB[r2] - tcntB[l2]) - (tcntA[r2] - tcntA[l2]);
		puts((sc - tc) % 3 == 0 ? "YES" : "NO");
	}


    return 0;
}   

Measured memory_bytes: 11600
#include <stdio.h>

int main(void) {
  int i, j, n, m, x, y, ans = 0;
  scanf("%d%d", &n, &m);
  int cnt[n];
  bool red[n];
  for(i = 0; i < n; ++i) cnt[i] = 1, red[i] = false;
  red[0] = true;
  for(i = 0; i < m; ++i) {
    scanf("%d%d", &x, &y);
    if(red[--x]) {
      if(cnt[x] == 1) red[x] = false;
      cnt[x]--, red[--y] = true, cnt[y]++;
    } else cnt[x]--, cnt[--y]++;
  }
  for(i = 0; i < n; ++i) if(red[i]) ++ans;
  printf("%d", ans);
  return 0;
}

Measured memory_bytes: 640
import java.util.*; 
import java.io.*;

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

        String S = next();
        char input[] = S.toCharArray();
        
        if(input[2] == input[3] && input[4] == input[5]){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

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

    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }
}

Measured memory_bytes: 32816
# -*- coding: utf-8 -*-

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
#        for line in sys.stdin:
#            lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    

    (n, k) = [int(e) for e in lines[0].split(' ')]
    p = [int(e) for e in lines[1].split(' ')]

    return (n, k, p)

def solve(n, k, p):

    current = sum([e + 1 for e in p[0:k]]) / 2
    result = current
    for i in range(n):

        if i + k < n: 
            next = current - (p[i] + 1) / 2 + (p[i+k] + 1) / 2
            if next > result:
                result = next
            current = next
        else:
            break


    return result

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r)
    else:
        print("%s" % result)

if __name__ == '__main__':

    main()
	

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

H_list_str = input().split()
H_list_int = list(map(int,H_list_str))

H_Count = 1

for i in range(1,N):
    for j in range(N-1):
        if H_list_int[i] < H_list_int[j]:
            break
        else:
            if j == i-1:
                H_Count += 1
            else:
                continue

print(H_Count)

Measured memory_bytes: 3060
#include<stdio.h>
int main(){
	char moji;
	int i;
	for(i=0;i<1200;i++){
		scanf("%c",&moji);
		if(moji=='\n') break;
		if(moji>='A' && moji<='Z'){
			moji=moji+32;
			printf("%c",moji);
		}else if(moji>='a' && moji<='z'){
			moji=moji-32;
			printf("%c",moji);
		}else{
			printf("%c",moji);
		}
	}
	printf("\n");
}
			
			
	


Measured memory_bytes: 2104
# ?????§?????????P???K??°?????????????????§???????????????????????????????
def check(P):
    i = 0
    for j in range(k):
        s = 0
        while s + w[i] <= P:
            s += w[i]
            i += 1
            if i == n:
                return n
    return i


def solve():
    left = 0
    right = sum(w) + 1 # ??????????????°???* 1????????????????????§??????
    while right - left > 1:
        mid = (left + right) / 2
        v = check(mid)  # mid == P ??¨???????????§???????????????????????????
        if v >= n:
            right = mid
        else:
            left = mid
            
    return right

if __name__ == "__main__":
    n, k = map(int, input().split())
    w = [int(input()) for i in range(n)]
    print(int(solve()))

Measured memory_bytes: 11652
#include <iostream>
#include <vector>
#include <string>
#include <cctype>
#include <sstream>

using namespace std;

string in[50000];
int lineNum, lineMax;

struct object {
  vector<string> key;
  vector<string> property;
  vector<object*> child;
};

object* parse_yaml(int parentIndent = -1) {
  object* obj = new object;

  while( lineNum < lineMax ) {
    int indent = 0;
    for( ;isspace(in[lineNum][indent]); indent++ );

    if( indent <= parentIndent ) break;
    
    int colon = in[lineNum].find(":");
    string key = in[lineNum].substr(indent, colon-indent);
    if( colon == in[lineNum].size()-1 ) {
      // object
      obj->key.push_back(key);
      obj->property.push_back("__ymobj");
      
      lineNum ++;
      // parse children
      obj->child.push_back(parse_yaml(indent));
    } else {
      // has property
      obj->key.push_back(key);
      obj->property.push_back(in[lineNum].substr(colon+2));
      obj->child.push_back(NULL); // NULLポインタを代入しないとセグフォ
      
      lineNum ++;
    }
  }
  
  return obj;
}

bool search( const object* root, const vector<string>vecQ, string& ans ) {
  
  // find object
  for(unsigned i=0; i<vecQ.size()-1; i++) { // "-1" means object(not string)
    bool ok = 0;
    for(unsigned j=0; j<root->key.size(); j++) {
      if(root->key[j] == vecQ[i]) {
	if(root->property[j] != "__ymobj") break; // found same string key with query object
	root = root->child[j];
	ok = 1;
	break;
      }
    }
    if(!ok) return false;
  }
  
  // find property
  for(unsigned i=0; i<root->key.size(); i++) {
    if(root->key[i]==vecQ.back()) {
      
      if(root->property[i] == "__ymobj") {
	ans = "object";
	return true;
      } else {
	ans = "string \"" + root->property[i] + "\"";
	return true;
      }
    }
  }
  
  return false;
}

void input_yaml() {
  lineMax = 0;
  for(int i=0; getline(cin, in[i]); i++, lineMax++);
}

int main() {
  
  string query;
  getline(cin, query);
  //replaceAll( query, ".", " " );
  for(unsigned i=0; i<query.size(); i++) if(query[i]=='.') query[i] = ' ';
  stringstream ss( query );
  vector<string> vecQuery;
  while( ss >> query ) vecQuery.push_back( query );
  
  input_yaml();
  
  lineNum = 0;
  object* yaml = parse_yaml();
  
  string ans;
  if( search( yaml, vecQuery, ans ) ) {
    cout << ans << endl;
  } else {
    cout << "no such property" << endl;
  }
  
  return 0;
}

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

int main(){
  string S;
  cin >> S;
  ll sum = 0;
  int len = S.size()-1;
  for (int tmp = 0; tmp < (1 << len); tmp++) {
    string str;
    str = S[0];
    rep(i,len){
      if ((tmp>>(len-1-i))&1) {
        sum += stoll(str);
        str = S[i+1];
      }
      else  str += S[i+1];
    }
    sum += stoll(str);
  }
  cout << sum << endl;
}

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

#define int            long long int
#define float          long double
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define inf            1e18
#define set_pre(x,y)   fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)

using namespace std;
int32_t main()
{
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    vector<int>dp(n);
    dp[0]=0;
    for(int i=1;i<n;i++){
        int idx=i-1;
        dp[i]=INT_MAX;
        while( idx+k>=i && idx>=0)
        {
            dp[i]=min(dp[i],dp[idx]+abs(v[i]-v[idx]));
            idx--;
        }
    }
    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define fs first
#define sc second
#define INF 1000000000
#define MOD 1000000007
#define EPS 0.00000001

struct R {
    int idx;
    string city;
    int score;
};

bool f(R &a, R &b){
    if(a.city == b.city) return a.score > b.score;
    return a.city < b.city;
}

int main() {
    int N; cin >> N;
    vector<R> V(N);
    for(int i=0; i<N; i++){
        string s;
        int p;
        cin >> s >> p;
        V[i].idx = i+1;
        V[i].city = s;
        V[i].score = p;
    }
    
    sort(V.begin(), V.end(), f);
    for(int i=0; i<N; i++){
        cout << V[i].idx << endl;
    }

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n,N) for(ll i=(n);i<(ll)N;i++)
#define p(s) cout<<(s)<<endl
#define ck(n,a,b) ((a)<=(n)&&(n)<=(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const ll mod=1e9+7;


int main() {
	ll n,m;
	cin>>n>>m;
	ll dog=1,mon=1;
	if(abs(n-m)>1) p(0);
	else{
		REP(i,1,n+1) {
			dog*=i;
			dog%=mod;
		}
		REP(i,1,m+1) {
			mon*=i;
			mon%=mod;
		}
		ll ans=(dog*mon)%mod;
		if(n==m) ans*=2;
		p(ans%mod);
	}
	return 0;
}


Measured memory_bytes: 256
def main():
    n, k = map(int, input().split())
    answer = 0
    for i in range(1, n + 1):
        start = i
        coin_toss_time = 0
        while start < k:
            coin_toss_time += 1
            start *= 2
        answer += pow(2, -coin_toss_time) / n
    print(answer)


if __name__ == '__main__':
    main()



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

void solver() {
  long long x;
  cin >> x;

  long long ans = (long long)(x / 500) * 1000;
  ans += (long long)(((x % 500) / 5) * 5);
  cout << ans << "\n";
  return;
}

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


Measured memory_bytes: 256
#C
N = int(input())
B = list(map(int,input().split()))
cnt = 0
for i in range(0,N-2):
    if  B[i] > B[i+1]:
        cnt += B[i+1]
    else:
        cnt += B[i]

cnt += B[N-2]+B[0]


print(cnt)
         

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, a, n) for (int i = a; i <= (n); ++i)

using namespace std;
using ll = long long;

/**
 * 桁数を求めます
 */
int number_of_digits(ll n) {
    int count = 0;
    while (n > 0) {
        n /= 10;
        count++;
    }
    return count;
}

int main() {
    ll N; cin >> N;
    
    int ans = number_of_digits(N);
    for(ll A = 1LL; A * A <= N; A++) {
        if (N % A != 0) continue;
        ll B = N / A;
        ans = min(ans, max(number_of_digits(A), number_of_digits(B)));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int a[n];
  rep(i,n) cin >> a[i];
  int b[n];
  if(n%2==0){
    rep(i,n/2){
      b[i] = a[n-1 - i*2];
    }
    rep(i,n/2){
      b[i+n/2] = a[2*i];
    }
  }
  else{
    rep(i,n/2+1){
      b[i] = a[n - 1 - i*2];      
    }
    rep(i,n/2){
      b[i+n/2+1] = a[1+2*i];
    }
  }
  rep(i,n) cout << b[i] << " ";
  cout << ""<<endl;
  return 0;
    

}


Measured memory_bytes: 3712
#include<iostream>
#include<vector>
using namespace std;
int n,m;
vector<int> list[200001];
bool flag=false;
void dfs(int v,int p,int d){
	if(v==n && d==2) flag=true;
	for(int i=0;i<list[v].size();i++){
		if(list[v][i]==p) continue;
		dfs(list[v][i],v,d+1);
	}
	return;
}
int main(){
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int a,b;
		cin >> a >> b;
		list[a].push_back(b);
	}

	dfs(1,-1,0);
	if(flag) cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
constexpr int INF = 1000000000;

int main() {
  while(1){
    int n;
    cin>>n;
    if(!n)break;
    vector<tuple<int,int,int>> v;
    REP(i,n) {
      int s,t,u;
      cin>>s>>t>>u;
      v.emplace_back(s,t,u);
    }
    int mn_itv = INF;
    int st_t = 0;
    REP(i,n) {
      int s,t,u;
      tie(s,t,u) = v[i];
      vector<int> p = {s, t, u};
      sort(ALL(p));
      do {
        int hi,mi,si;
        hi = p[0];
        mi = p[1];
        si = p[2];
        REP(k,60) {
          int kh = (hi + k) % 60;
          int km = (mi + k) % 60;
          int ks = (si + k) % 60;
          if (kh % 5 != km / 12) continue;
          int st = (kh / 5) * 3600 + km * 60 + ks;
          int itv = 0;
          REP(j,n) {
            if (i==j) continue;
            int sj,tj,uj;
            tie(sj,tj,uj) = v[j];
            vector<int> q = {sj, tj, uj};
            sort(ALL(q));
            int l_mn_itv = INF;
            do {
              int hj = q[0];
              int mj = q[1];
              int sj = q[2];
              REP(l,60) {
                int lh = (hj + l) % 60;
                int lm = (mj + l) % 60;
                int ls = (sj + l) % 60;
                if (lh % 5 != lm / 12) continue;
                int tm = (lh / 5) * 3600 + lm * 60 + ls;
                if (tm < st) continue;
                l_mn_itv = min(l_mn_itv, tm-st);
              }
            } while(next_permutation(ALL(q)));
            itv = max(itv, l_mn_itv);
          }
          if (itv < mn_itv) {
            mn_itv = itv;
            st_t = st;
          } else if (itv == mn_itv) {
            st_t = min(st_t, st);
          }
        }
      } while(next_permutation(ALL(p)));
    }
    int hs = st_t / 3600;
    int ms = (st_t % 3600) / 60;
    int ss = st_t % 60;
    int ed_t = st_t + mn_itv;
    int he = ed_t / 3600;
    int me = (ed_t % 3600) / 60;
    int se = ed_t % 60;
    printf("%02d:%02d:%02d %02d:%02d:%02d\n", hs, ms, ss, he, me, se);
  }
  return 0;
}

Measured memory_bytes: 3152
#include <iostream>
#include <algorithm>
using namespace std;
bool binary_search(int val, int a[], int n){
    int first = 0, last = n;
    while(last - first > 1){
        int middle = (last+first)/2;
        if(a[middle] <= val) first = middle;
        else last = middle;
    }
    return (a[first] == val);
}
 int main(){
    int n; cin >> n;
    int a[n]; for(int i = 0; i < n; ++i) cin >> a[i];
    int q; cin >> q;
    int b[q]; for(int i = 0; i < q; ++i) cin >> b[i];
    sort(a,a+q);
    int ans = 0;
    for(int i = 0; i < q; ++i){
        if(binary_search(b[i], a, n)) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct task {
  int a; // day after
  int b; // repair
};

bool compare_by_day_reverse(const task &t1, const task &t2) {
  return t1.a < t2.a;
}

class CompareByRepaireAsc {
public:
  bool operator()(const task &t1, const task &t2) const {
    return t1.b < t2.b;
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  vector<task> tasks;
  for (int i = 0; i < N; ++i) {
    task t;
    cin >> t.a >> t.b;
    tasks.push_back(t);
  }
  sort(tasks.begin(), tasks.end(), compare_by_day_reverse);

  int next_add = 0;
  long long sum = 0;
  priority_queue<task, vector<task>, CompareByRepaireAsc> q;
  for (int m = M; m >= 0; --m) {
    int left_day = M - m;
    while (next_add < N) {
      task t = tasks[next_add];
      if (t.a <= left_day) {
	q.push(t);
	next_add++;
      } else {
	break;
      }
    }
    if (!q.empty()) {
      task best_t = q.top();
      q.pop();
      sum += best_t.b;
    }
  }
  cout << sum << "\n";
  return 0;
}


Measured memory_bytes: 2548