akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.math.*;
import java.util.*;
public class Main{

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		String S = input.next();
		int N = S.length();
		int[] ans = new int[N];
		int curIndex = 0;
		while (curIndex < N) {
			int numLeft = 0;
			int numRight = 0;
			while (S.charAt(curIndex)=='R') {
				numRight++;
				curIndex++;
				if (curIndex==N) break;
			}
			//curIndex--; //After last ever L/R, curIndex is incremented which causes array 
			//out of bounds
			int R = curIndex-1;
			while (S.charAt(curIndex)=='L') {
				numLeft++;
				curIndex++;
				if (curIndex==N) break;
			}
			int left = numLeft;
			int right = numRight;
			if ((left+right)%2==0) { //Children cascade into adjacent numbers as close to 
				//each other as possible
				int sum = left+right;
				left=sum/2;
				right=sum/2;
			}else {
				int sum = left+right;
				if (right%2==1) { //The greater number is given to the R/L count with odd parity
					right=sum/2;
					left=sum-right;
				}else {
					left=sum/2;
					right=sum-left;
				}
			}
			ans[R]=left;
			ans[R+1]=right; //Children moving swaps squares 
			if (curIndex==N-1) break;
		}
		for (int i = 0; i < N; i++)
			System.out.print(ans[i]+" ");
	}
}


Measured memory_bytes: 42436
/********   All Required Header Files ********/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
// ****  All Required define Pre-Processors and typedef Constants *******/
#define mem(a, b) memset(a, (b), sizeof(a))
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define fl(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)

#define fi(it, l) for (auto it = l.begin(); it != l.end(); it++)

#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
const double pi=acos(-1.0);
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> dmap;
typedef set<int> dset;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
/********** solver function **********/
int dfs(int u, vector<vector<int>>&g, vector<int> &dp,int p=-1){
    // if( )
    // visited[u]=true;
    if( dp[u]!=-1) return dp[u];
    int ans=0;
    for( int i=0;i<g[u].size();i++){
        if( g[u][i]!=p){
            // cout<<" ans"<<ans<<"|";
            ans=max(ans,1+dfs( g[u][i], g,dp,u));
        }
    }
	return dp[u]= ans;
}
/********** Main()  function **********/
int main()
{std::ios::sync_with_stdio(false);
	int n,m;
    cin>>n>>m;
    // vector<bool> visited(n, false);
    vector<int> dp(n+1,-1);
    vector<vector<int>>g(n);
    for( int i=0;i<m;i++){
        int u, v;
        cin>>u>>v;
        g[u-1].push_back(v-1);
    }
    int ma=0;
    for( int i=0;i<n;i++){
            int x=dfs(i, g, dp);
           ma=max(ma, x);
    }
    cout<<ma<<endl;
	return 0;
}

Measured memory_bytes: 11980
#include<bits/stdc++.h>
using namespace std;
int n,k;
struct treaps
{
	int son[1000100][2],num[1000100],size[1000100],ran[1000100];
	long long dl[1000100],dr[1000100];
	int tt;
	long long getl(int root)
	{
		while (son[root][0]) root=son[root][0];
		return dl[root];
	}
	long long getmin(int root)
	{
		long long ans=dr[root];
		if (son[root][0]) ans=min(ans,getmin(son[root][0]));
		if (son[root][1]) ans=min(ans,getmin(son[root][1]));
		return ans;
	}
	int newnode(int num_,int size_,long long dl_,long long dr_)
	{
		tt++;
		son[tt][0]=son[tt][1]=0;ran[tt]=rand();
		num[tt]=num_;size[tt]=size_;dl[tt]=dl_;dr[tt]=dr_;
		return tt;
	}
	int merge(int s,int t)
	{
		if (!s) return t;if (!t) return s;
		if (ran[s]>ran[t])
		{
			size[s]+=size[t];
			son[s][1]=merge(son[s][1],t);
			return s;
		}
		else
		{
			size[t]+=size[s];
			son[t][0]=merge(s,son[t][0]);
			return t;
		}
	}
	pair<int,int> split(int root,int k)
	{
		if (!root) return make_pair(0,0);
		if (k<=size[son[root][0]])
		{
			pair<int,int> p=split(son[root][0],k);
			son[root][0]=p.second;size[root]=size[son[root][0]]+size[son[root][1]]+num[root];
			return make_pair(p.first,root);
		}
		if (k>=size[son[root][0]]+num[root])
		{
			pair<int,int> p=split(son[root][1],k-size[son[root][0]]-num[root]);
			son[root][1]=p.first;size[root]=size[son[root][0]]+size[son[root][1]]+num[root];
			return make_pair(root,p.second);
		}
		k-=size[son[root][0]];
		int a=newnode(k,k,dl[root],dl[root]),b=newnode(num[root]-k,num[root]-k,dr[root],dr[root]);
		if (dl[root]>dr[root]) {dr[a]=dl[root]-k+1;dl[b]=dl[root]-k;}
		return make_pair(merge(son[root][0],a),merge(b,son[root][1]));
	}
}treap;
int main()
{
	scanf("%d%d",&n,&k);long long sum=0;
	int root=treap.newnode(k,k,0,0);
	for (int i=1;i<=n;i++)
	{
		int len,tp;scanf("%d%d",&len,&tp);
		sum+=len;
		if (tp==1)
		{
			if (len*2>k) {puts("-1");return 0;}
			pair<int,int> p=treap.split(root,1),q=treap.split(p.second,len*2-1);
			q.second=treap.merge(q.second,p.first);
			long long y=treap.getl(q.second);
			root=treap.merge(q.second,treap.newnode(len*2-1,len*2-1,y+len*2-1,y+1));
		}
		else
		{
			pair<int,int> p=treap.split(root,len*2%k);
			root=treap.merge(p.second,p.first);
		}
	}
	printf("%lld\n",sum*2+treap.getmin(root));
}
			

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

typedef pair<int, int> P;
#define INF (1<<31-1)
#define ll long long

// 連続する長さを数えてpairをvector		{1,2,1,1,3,2,2}=>{(1,1),(2,1),(1,2),(3,1),(2,2)}
vector<P> count_runlength(int*a, int*b){
	vector<P> v;
	int p = *a;
	int l = 0;
	while (1){
		a++;
		l++;
		if (a == b) break;
		if (p != *a){
			v.push_back(P(p, l));
			l = 0;
			p = *a;
		}
	}
	v.push_back(P(p, l));
	return v;
}

int main(){

	int N;
	int p[100001];

	cin >> N;
	for (int i = 1; i <= N; i++){
		cin >> p[i];
		if (p[i] == i) p[i]=1;
		else p[i] = 0;
	}

	int result = 0;
	auto v = count_runlength(p + 1, p + N+1);
	for (auto i = v.begin(); i != v.end(); i++){
		if (i->first == 1) result += (i->second + 1) / 2;
	}

	cout << result << endl;


	return 0;
}


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

using namespace std;

int main(void) {
    int n, a, mina = 1001, maxa = -1;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        mina = min(a, mina);
        maxa = max(a, maxa);
    }
    cout << maxa - mina << endl;
    
    return 0;
}

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

#define mp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> l4;



vector<char> vs;
char s[100001];
int k;
deque<char> dq;
int nxt[10];
bool forbid[10]={0};
int main()
{
  scanf("%s %d", s, &k);
  for (int i = 0; i < k; ++i)
    {
      int x;
      scanf("%d", &x);
      forbid[x] = true;
    }
  //preprocess nxt[10]
  {
    int p = 0;
    for (int i = 0; i < 10; ++i)
      {
	if (p < i)
	  p = i;
	while (p < 10 && forbid[p])
	  ++p;
	if (p == 10)
	  nxt[i] = -1;
	else
	  nxt[i] = p;
      }
  }
  int len = strlen(s);
  for (int i = 0; i < len; ++i)
    dq.push_back(s[i]);
  for (int i = 0; i < dq.size(); ++i)
    {
      if (nxt[dq[i]-'0'] == -1)
	{
	  int pos = i;
	  --i;
	  while (i >= 0)
	    {
	      if (dq[i] < '9' && nxt[dq[i]-'0'+1]!=-1)
		{
		  dq[i] = nxt[dq[i]-'0'+1]+'0';
		  break;
		}
	      --i;
	    }
	  if (i < 0)
	    {
	      for (int j = 0; j < dq.size(); ++j)
		dq[j] = '0'+nxt[0];
	      dq.push_front(nxt[1]+'0');
	    }
	  else
	    {
	      for (int j = i+1; j < dq.size(); ++j)
		dq[j] = nxt[0]+'0';
	    }
	  break;
	}
      else if (nxt[dq[i]-'0']+'0' > dq[i])
	{
	  dq[i] = nxt[dq[i]-'0']+'0';
	  for (int j = i+1; j < dq.size(); ++j)
	    dq[j] = nxt[0]+'0';
	  break;
	}
    }
  for (int i = 0; i < dq.size(); ++i)
    putchar(dq[i]);
  puts("");
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i < (n); i++)

int main(){
    char c;
    cin >> c;
    cout << char(c+1) << endl;
}

Measured memory_bytes: 256
def gets_arrays(n)
  ans = []
  for i in 1..n
    ans << gets.delete("\n").split('')
  end
  ans
end

h, w = gets.split.map(&:to_i)
swss = gets_arrays(h)
m = 0
for i in 0..(h - 1)
  sws  = swss[i]
  for j in 0..(w - 1)
    if sws[j] == '#'
      if i == 0
        if j == 0
          b = swss[i + 1][j]
          d = sws[j + 1]
        elsif j == w - 1
          b = swss[i + 1][j]
          c = sws[j - 1]
          if b == '.' && d == '.'
            m += 1
            break
          end
        else
          b = swss[i + 1][j]
          c = sws[j - 1]
          d = sws[j + 1]
          if b == '.' && c == '.' && d == '.'
            m += 1
            break
          end
        end
      elsif i == h - 1
        if j == 0
          a = swss[i - 1][j]
          d = sws[j + 1]
          if a == '.' && d == '.'
            m += 1
            break
          end
        elsif j == w - 1
          a = swss[i - 1][j]
          c = sws[j - 1]
          if a == '.' && c == '.'
            m += 1
            break
          end
        else
          a = swss[i - 1][j]
          c = sws[j - 1]
          d = sws[j + 1]
          if a == '.' && c == '.' && d == '.'
            m += 1
            break
          end
        end
      elsif j == 0
        a = swss[i - 1][j]
        b = swss[i + 1][j]
        d = sws[j + 1]
        if a == '.' && b == '.' && d == '.'
          m += 1
          break
        end
      elsif j == w - 1
        a = swss[i - 1][j]
        b = swss[i + 1][j]
        c = sws[j - 1]
        if a == '.' && b == '.' && c == '.'
          m += 1
          break
        end
      else
        a = swss[i - 1][j]
        b = swss[i + 1][j]
        c = sws[j - 1]
        d = sws[j + 1]
        if a == '.' && b == '.' && c == '.' && d == '.'
          m += 1
          break
        end
      end
    end
  end
end
if m == 0
  puts 'Yes'
else
  puts 'No'
end

Measured memory_bytes: 3836
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
//const ll MOD = 1000000007;
const ll MOD = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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; }
//template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<int> ma1(N), ma2(N);
    ma1[0] = A[0];
    ma2[N-1] = A[N-1];
    for(int i=1;i<N;i++) ma1[i] = max(ma1[i-1], A[i]);
    for(int i=N-2;i>=0;i--) ma2[i] = max(ma2[i+1], A[i]);
    REP(i,N){
        if(i == 0) cout << ma2[i+1] << endl;
        else if(i == N-1) cout << ma1[i-1] << endl;
        else cout << max(ma1[i-1], ma2[i+1]) << endl;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    // int T; cin >> T; REP(t,T) solve();
}


Measured memory_bytes: 3968
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <istream>
#define rep0(i,n) for (int i = 0; i <= (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define vec vector<int>a(n)
#define soot(a) sort(a.begin(),a.end())
/*int n;
cin >> n;
vector<int>a(n);
rep0(i, n - 1)cin >> a[i];*/
using namespace std;
int main() {
	int n,b;
	cin >> n >> b;
	int ans = n * 2 + b * 2;
	cout << n*b<<" "<<ans<< endl;
	return 0;
}


Measured memory_bytes: 3040
import math

n = input()
a = list(map(int, input().split()))

# default
sum = 0
for i in range(len(a)):
    if i == 0:
        sum += abs(a[i])
    else :
        sum += abs(a[i]-a[i-1])
sum += abs(a[i])
baseSum = sum

for i in range(len(a) -1):
    if i == 0 :
        print(baseSum - ( abs(a[0]) + abs(a[1]-a[0]) ) + abs(a[1]))
    else :
        print(baseSum - ( abs(a[i+1]-a[i]) + abs(a[i]-a[i-1]) ) + abs(a[i+1]-a[i-1]))
i+=1
print(baseSum - ( abs(0-a[i]) + abs(a[i]-a[i-1]) ) + abs(0-a[i-1]))


Measured memory_bytes: 14048
function makeHist(numbers) {
    const hist = new Map()

    for (const n of numbers) {
        if (hist.has(n)) {
            hist.set(n, hist.get(n) + 1)
        }
        else {
            hist.set(n, 1)
        }
    }

    return hist
}

function main(lines) {
    const [N] = parseNumberLine(lines[0])
    const numbers = parseNumberLine(lines[1])
    const [Q] = parseNumberLine(lines[2])
    const operationLines = lines.slice(3)

    const hist = makeHist(numbers)

    let result = 0
    hist.forEach((v, k) => {
        result += k * v
    })

    for (let i = 0; i < Q; ++i) {
        const [B, C] = parseNumberLine(operationLines[i])

        if (hist.has(B)) {
            const count = hist.get(B)
            hist.delete(B)

            if (hist.has(C)) {
                hist.set(C, hist.get(C) + count)
            }
            else {
                hist.set(C, count)
            }
            result += (C - B) * count
        }

        console.log(result)
    }
}

function parseNumberLine(line, radix = 10) {
    return line.split(/\s+/).map(_ => parseInt(_, radix))
}

main(require("fs").readFileSync("/dev/stdin", "utf8").split("\n"))


Measured memory_bytes: 66632
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <ios> 
#include <iomanip>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
	int n; cin >> n;
    cout << (int)pow((double)(int)sqrt((double)n), 2.0) << endl;
	return 0;
}

Measured memory_bytes: 256
until (n = gets.to_i) == 0
  puts n.times.reduce(gets.chomp) {|s|
    a = r = nil
    res = ''
    (s << 0).each_char {|c|
      if c == a
        r += 1
      else
        res << (r || '').to_s << (a || '')
        a = c
        r = 1
      end
    }
    res
  }
end

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

using namespace std;

int main(){
  	int N, cnt = 0;
  	cin >> N;
  	
  	vector<int> p(N);
  	for(int i = 1; i <= N; i++){
    	cin >> p[i-1];
      	if(p[i-1] != i){
        	cnt++;
        }
    }
  
  	if(cnt == 0 || cnt == 2){
    	cout << "YES" << endl;
    }else{
    	cout << "NO" << endl;
    }
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>
#include <random>
#include <functional>
using namespace std;
#define all(x) (x).begin(), (x).end()
 
const int N = 500000;
const long long MOD = 1e9 + 7;
 
int n, m;
vector<string> s;
long long ans = 0;
 
void R()
{
    vector<string> f(m, string(n, ' '));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            f[m - 1 - j][i] = s[i][j];
        }
    }
    swap(n, m);
    s = f;
    return;
}
 
void F()
{
    vector<vector<int> > summ(n, vector<int>(m));
    function<int(int, int)>G = [&](int i, int j)
    {
        if (j < 0 || j + i < 0 || i >= n) return 0;
        if (i < 0)
        {
            j -= -i;
            i += -i;
        }
        return summ[i][j];
    };
    function<int(int, int)>M = [&](int i, int j)
    {
        if (i < 0 || j < 0 || i >= n || j >= m) return 0;
        return (int)(s[i][j] == '#');
    };
    for (int si = 0; si < n + m - 1; si++)
    {
        for (int i = si; i >= 0; i--)
        {
            int j = si - i;
            if (0 <= i && i < n && 0 <= j && j < m)
            {
                summ[i][j] = G(i + 1, j - 1) + M(i, j);
            }
        }
    }
    for (int s = 0; s < n + m - 1; s++)
    {
        for (int i1 = 0; i1 <= s; i1++)
        {
            for (int i2 = 0; i2 <= s; i2++)
            {
                int j1 = s - i1, j2 = s - i2;
                if (j1 < j2 && 0 <= j1 && j1 < m && 0 <= j2 && j2 < m && M(i1, j1) && M(i2, j2))
                {
                    int k = j2 - j1;
                    int i3 = i2, j3 = j1 - k;
                    int i4 = i2 - k, j4 = j1;
                    i3++, j3--;
                    ans += G(i4, j4) - G(i3, j3);
                }
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (int k = 1; k <= 300; k++)
            {
                if (M(i + k, j) && M(i, j + k) && M(i - k, j)) ans--;
            }
        }
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    s.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    F();
    R();
    F();
    R();
    F();
    R();
    F();
    cout << ans;
}

Measured memory_bytes: 788
#include <stdio.h>

int main(){
	unsigned char Go[100000];
	int i,j,k;
	int n;
	int sum;
	
	while(1){
		scanf("%d\n",&n);
		if(n==0)break;
		for(i=0;i<n;i++){
			scanf("%d\n",&Go[i]);
			if(i%2&&Go[i]^Go[i-1]){
				for(k=i-1;k>=0;k--){
					if(Go[k]==Go[i])break;
					Go[k]=Go[i];
				}
			}
		}
		sum=0;
		for(i=0;i<n;i++)sum+=Go[i];
		printf("%d\n",n-sum);
	}
	return 0;
}

Measured memory_bytes: 700
def solve(string):
    a, b, q, *stx = map(int, string.split())
    s = [-10**10] + stx[:a] + [2 * 10**10]
    t = [-10**10] + stx[a:a + b] + [2 * 10**10]
    x = dict([])
    i_s = 0
    i_t = 0
    for _x in sorted(set(stx[-q:])):
        while s[i_s] < _x:
            i_s += 1
        while t[i_t] < _x:
            i_t += 1
        ls, rs = s[i_s - 1], s[i_s]
        lt, rt = t[i_t - 1], t[i_t]
        r_max = max(rs, rt)
        l_min = min(ls, lt)
        x[_x] = min([
            r_max - _x, _x - l_min, rt - ls + min(rt - _x, _x - ls),
            rs - lt + min(rs - _x, _x - lt)
        ])
    return "\n".join([str(x[_x]) for _x in stx[-q:]])


if __name__ == '__main__':
    n, m, l = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, l) + '\n'.join([input() for _ in range(n + m + l)])))


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

int main(void) {

    int K, T; cin >> K >> T;
    vector<int> a(T);
    int max_ind = 0;
    int ans = 0;
    cin >> a[0];
    for (int i = 1; i < T; i++) {
        cin >> a[i];
        if (a[i] > a[max_ind]) {
            ans += a[max_ind];
            max_ind = i;
        } else {
            ans += a[i];
        }
    }
    if (a[max_ind]-ans-1 < 0) {
        ans = 0;
    } else {
        ans = a[max_ind]-ans-1;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int_fast64_t read(){int_fast64_t x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
inline string read_s(){string s="";char c=getchar();while(c<'!'||c>'~'){c=getchar();}while(c>='!'&&c<='~'){s+=c;c=getchar();}return s;}
void Main(){
    double ans1;
    int ans2;
    double W = read(), H = read(), x = read(), y = read();
    ans1 = W*H/2;
    ans2 = (x*2 == W && y*2 == H) ? 1 : 0;
    printf("%lf %d\n", ans1, ans2);
}
int main(){cin.tie(nullptr);ios::sync_with_stdio(false);Main();return 0;}

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

#define lli long long int
#define LLI(n) lli n; cin >> n;
#define STR(n) string n; cin >> s;
#define Sort(n) sort(n.begin(), n.end());
#define Reve(n) reverse(n.begin(), n.end());
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define C45(n) (n + 1) / 2
#define OUT(n) cout << n << endl;
#define SRC(n, c)for (lli i = 0;i < s.size(); i++) { if (s.at(i) == c) { n++; } };

//素数
bool IsPrime(lli num)
{
  if (num < 2) return false;
  else if (num == 2) return true;
  else if (num % 2 == 0) return false;
  long double sqrtNum = sqrt(num);
  for (lli i = 3; i <= sqrtNum; i += 2)
  {
    if (num % i == 0)return false;
  }
  return true;
}
//各桁の和
lli Sum(lli n)
{
  lli sum=0;
  if (n<0) return 0;
  while (n>0)
  {
    sum += n%10;
    n /= 10;
  }
  return sum;
}

int main(void)
{
  ios::sync_with_stdio(false);
  STR(s);
  cout << s[0] << s.size()-2 << s[s.size()-1] << endl;
  return 0;
}


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

int dp[100010];

int main() {
  int N;
  scanf("%d", &N);

  // 初期化
  for (int i = 1; i <= 100000; i++) {
    dp[i] = 100000;
  }

  // dp[0]の初期値は0
  dp[0] = 0;
  for (int n = 1; n <= 100000; n++) {
    int power = 1;
    while (power <= N) {
      if (n - power >= 0) dp[n] = min(dp[n], dp[n - power] + 1);
      power *= 6;
    }
    power = 1;
    while (power <= N) {
      if (n - power >= 0) dp[n] = min(dp[n], dp[n - power] + 1);
      power *= 9;
    }
  }

  printf("%d", dp[N]);
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using std::cin;
using std::cout;
using std::endl;
using std::vector;

void swap(int *a, int *b) {
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
	return;
}

void order_sort(vector<int> &v, vector<int> &o, int s, int e) {
	int p = (s+e)/2;

	for (int i = 0; i < p; i++) {
		if (v[i] > v[p]) {
			swap(&v[i],&v[p]);
			swap(&o[i],&o[p]);
		}
	}
	for (int i = p; i < e; i++) {
		if (v[i] < v[p]) {
			swap(&v[i],&v[p]);
			swap(&o[i],&o[p]);
		}
	}

	if (s == p || e == p) {
		return;
	}
	order_sort(v,o,s,p);
	order_sort(v,o,p,e);
}

int main(void) {
	int n,m,a;
	cin >> n;
	cin >> m;
	cin >> a;
	
	while (n!=0||m!=0||a!=0) {
		vector<int> res(n);
		vector<int> h(m),p(m),q(m),order(m);
		int ind;
		
		for (int i = 0; i < n; i++) {
			res[i] = i + 1;
		}

		for (int i = 0; i < m; i++) {
			cin >> h[i];
			order[i] = i;
			cin >> p[i];
			cin >> q[i];
		}

		order_sort(h,order,0,h.size());

		for (int i = 0; i < m; i++) {
			ind = order[i];
			swap(&res[p[ind]-1],&res[q[ind]-1]);
		}
			
		cout << res[a-1] << endl;

		cin >> n;
		cin >> m;
		cin >> a;
	}

	return 0;
}

Measured memory_bytes: 3000
#include <iomanip>
#include <random>
#include <time.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <typeinfo>
#include <iostream>
using namespace std;
int main()
{
	long long int n, cnt[100][30] = {}, a[30], yan;
	string s[100], ans = "";
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		for (int j = 0; j < s[i].size(); j++) {
			yan = s[i][j] - 'a' + 1;
			cnt[i][yan]++;
			a[yan] = cnt[1][yan];
		}
	}
	for (int i = 1; i < 27; i++) {
		for (int j = 1; j <= n; j++) {
			a[i] = min(a[i], cnt[j][i]);
		}
	}
	for (int i = 1; i < 27; i++) {
		for (int j = a[i]; j > 0; j--) {
			ans += 'a' + i - 1;
			}
	}
	cout << ans << endl;
	return 0;
}


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

mt19937_64 llrand((int) chrono::steady_clock::now().time_since_epoch().count());

#define st first
#define nd second
#define pb push_back

#ifndef ONLINE_JUDGE
  #define db(x) cerr << #x << " == " << x << endl
  #define dbs(x) cerr << x << endl
  #define _ << ", " <<
#else
  #define db(x) ((void)0)
  #define dbs(x) ((void)0)
#endif

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;

const int INF = 0x3f3f3f3f, MOD = 1e9+7;
const int N = 1e5+5;

int A, B, C, D;

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> A >> B >> C >> D;
  while(true) {
    C -= B;
    if(C <= 0) break;
    A -= D;
    if(A <= 0) break;
  }
  if(A <= 0) cout << "No\n";
  else cout << "Yes\n";
}


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

typedef long long ll;
ll comb(int n, int r) {
  std::vector<std::vector<long long>> v(n + 1,std::vector<long long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v[n][r];
}

int main(void){
  cout << setprecision(10);
  int N,A,B;
  cin >> N >> A >> B;
  map<ll, int> m;
  ll min_val = 0;
  for(int i = 0; i < N; i++){
    ll tmp;
    cin >> tmp;
    tmp *= -1;
    if(m.count(tmp) == 0){
      m[tmp] = 1;
    } else { 
      m[tmp] += 1;
    }
    if(tmp < min_val){
      min_val = tmp;
    }
  }
  
  int num = 0;
  ll  sum = 0;
  ll last_num = 0;
  for(auto x: m){
    if(num + x.second >= A){
      last_num = x.first;
      sum += -x.first * (A - num);
      break;
    } else { 
      num += x.second;
      sum += -x.first * x.second;
    }
  }
  cout << setprecision(20) << (double)sum / (double)A << endl;

  // A - num 個を、v[last_num]個から選ぶ
  int p = A - num;
  int q = m[last_num];
  ll ans = 0;
  if(num == 0){ // 最初が全ての場合, A個でもB個でも同じ
    for(int i = A; i <= min(B, q); i++){
      ans += comb(q, i);
    }
  } else { 
    ans = comb(q, p);
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
n, k = map(int,input().split())
s = input()
ha = []
owa = []
ju = 0
for i in range(len(s)) :
    if s[i] == "1" :
        if ju == 0 :
            ha.append(i)
            ju = 1
    else :
        if ju == 1 :
            owa.append(i - 1)
            ju = 0
if not ha :
    print(len(s))
else :
    if ha[0] != 0 :
        ha.insert(0,0)
        owa.insert(0,0)
    owa.append(len(s)-1)
    if len(ha) != len(owa) :
        ha.append(len(s) - 1)
    #print(ha,owa)
    dai = 0
    for i in range(len(owa) - k) :
        dai = max(dai,owa[i+k] - ha[i] + 1)
    if len(ha) > k :
        print(dai)
    else :
        print(len(s))


Measured memory_bytes: 7200
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long 
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;
#define FORR(x,arr) for(auto& x:arr)

ll mo=1000000007;
ll comb(ll N_, ll C_) {
    const int NUM_=100043;
    static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
    if (fact[0]==0) {
        inv[1]=fact[0]=factr[0]=1;
        for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
        for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
    }
    if(C_<0 || C_>N_) return 0;
    return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
    }
int32_t main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall 
	oneforall

	ini(n);
	ini(n1);
	int morty[n][n1];
	FOR(i,0,n){
		FOR(i1,0,n1){
			in(morty[i][i1]);
		}
	}
	int tmp = 0;
	vpii rick;
	vpii rick1;
	FOR(i,0,n){
		FOR(i1,0,n1-1){
			if(morty[i][i1]%2){
				rick.push_back({i+1,i1+1});
				rick1.push_back({i+1,i1+2});
				tmp++;
				morty[i][i1+1]++;
			}
		}
	}
	FOR(i,0,n-1){
		if(morty[i][n1-1]%2){
			tmp++;
			rick.push_back({i+1,n1});
				rick1.push_back({i+2,n1});
				morty[i+1][n1-1]++;
		}
	}
	out(tmp);
	FOR(i,0,rick.size()){
		out(rick[i].first,rick[i].second,rick1[i].first,rick1[i].second);
	}















	return 0;
}

Measured memory_bytes: 8164
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200000;
int n;
int a[N+1];
int buc[N+1];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],buc[a[i]]++/*装进桶*/;
	int ans=0;
	for(int i=1;i<=n;i++)ans+=buc[i]*(buc[i]-1)/2;//不带限制时的答案 
	for(int i=1;i<=n;i++)cout<<ans-(buc[a[i]]-1)<<"\n";
	return 0;
}

Measured memory_bytes: 4736
import java.util.*;
import java.io.*;
class Main {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		System.out.println((x / 3600) + ":" + (x % 3600 / 60) + ":" + (x % 60));
	}
}


Measured memory_bytes: 26272
//Vivek
#pragma optimize("", off)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:36777216")
#include <bits/stdc++.h>

#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long 
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz(i) int(i.size())
#define setto(n) cout << fixed << setprecision(n)
#define fi first
#define se second
#define inf LONG_MAX
const int mod = 2000000007;

using namespace std;

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}
template<class T> void smax(T& a, T val) {if (a < val) a = val;}
template<typename T>inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v){bool first = true;os << "[";for(auto i: v){if(!first)os << ", ";os << i;first = false;}return os << "]";}

const int N = 2*1e5 + 10;

#define int ll
int x1,x2,y1_,y2,d;

ll dis(int x, int y, int x2, int y2){
	return (x-x2)*1LL*(x-x2) + (y-y2)*1LL*(y-y2);
}


#define x first
#define y second
#define Point pair<int, int>
int orientation(Point p1, Point p2, Point p3)
{
    // See 10th slides from following link for derivation
    // of the formula
    int val = (p2.y - p1.y) * (p3.x - p2.x) -
              (p2.x - p1.x) * (p3.y - p2.y);
 
    return (val > 0)? 1: 2; // clock or counterclock wise
}

main(){_
	cin>>x1>>y1_>>x2>>y2;

	ll currdis = dis(x1,y1_,x2,y2);


if(0){
	for (int i = -500; i <= 500; ++i)
	{
		int f = 0;
		for (int j = -500; j <= 500; ++j)
		{
			if(dis(i,j,x1,y1_) == currdis and dis(x2,y2,i,j) == 2LL*currdis){
				cout<<i<<' '<<j<<' ';
				f = 1;
				break;
			}
		}
		if(f)break;
	}

	for (int i = -500; i <= 500; ++i)
	{
		int f = 0;
		for (int j = -500; j <= 500; ++j)
		{
			if(dis(i,j,x2,y2) == currdis and dis(x1,y1_,i,j) == 2LL*currdis){
				cout<<i<<' '<<j<<' ';
				f = 1;
			}
		}
		if(f) break;
	}
}

#define mp make_pair
else{
	for (int i = -500; i <= 500; ++i)
	{
		int f = 0;
		for (int j = -500; j <= 500; ++j)
		{
// int orientation(Point p1, Point p2, Point p3)
			if(dis(i,j,x2,y2) == currdis and dis(x1,y1_,i,j) == 2LL*currdis and orientation(mp(x1,y1_), mp(x2,y2), mp(i,j)) == 2){
				cout<<i<<' '<<j<<' ';
				f = 1;
			}
		}
		if(f) break;
	}

	for (int i = -500; i <= 500; ++i)
	{
		int f = 0;
		for (int j = -500; j <= 500; ++j)
		{
			if(dis(i,j,x1,y1_) == currdis and dis(x2,y2,i,j) == 2LL*currdis and (orientation(mp(x1,y1_), mp(x2,y2), mp(i,j)) == 2)){
				cout<<i<<' '<<j<<' ';
				f = 1;
				break;
			}
		}
		if(f)break;
	}

}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>//数据输入输出流
#include <cstring>//字符串操作函数
#include <cstdio>//C的输入输出
#include <cstdlib>//定义杂项函数及内存分配函数
#include <cmath>//C中的数学函数
#include <string>//c++中的string类 他不能用strcpy等c函数去操作
#include <vector>//STL vetor
#include <list>//STL list
#include <map>// STL map
#include <queue>// STL queue
#include <stack>//sTL stack
#include <bitset>//bitset可按位定义串
//比如：bitset <1000> all;定义一个1000位的串
#include <algorithm>//STL各种算法 比如 swap sort merge max min 比较
#include <numeric>//常用数字操作 一般和algorithm搭配使用
#include <functional>//STL定义运算函数（代替运算符）
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define LOCAL
#define zeros(a,n) memset(a,0,(n)*sizeof(a[0]))
const int modn = 1e9+7;
int mod(int x) { return x<0?x+modn:x<modn?x:x-modn; }

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int x;
    cin>>x;
    int y=x/500, z=(x-500*y)/5;
    cout<<1ll*y*1000+1ll*z*5<<endl;
    return 0;
}



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    EACH(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    REP(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    REP(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

int main() {
    ll A, B, C, D; cin >> A >> B >> C >> D;
    cout << max(A*B, C*D) << endl;
    return 0;
    vector<ll> v(3);
    rep(i, 3) cin >> v[i];
    sort(v.begin(), v.end());
    cout << v[0] + v[2] - v[1] << endl;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define SHAPE 7

int main() {
  long int a[7];
  int i;
  for (i = 0; i < 7; i++) {
    scanf(" %ld", &a[i]);
  }
  long int sum = 0;
  int sum1;

  sum1 = a[0] % 2 + a[3] % 2 + a[4] % 2;
  if (sum1<=1||a[0]*a[3]*a[4]==0) {
    sum += (a[0] / 2) * 4;
    sum += (a[3]/2)*4;
    sum += (a[4] / 2) * 4;
  }
  else if (sum1 == 2){
    sum += (a[0] + a[3] + a[4] - 4) * 2 + 6;
  }
  else {
    sum += (a[0] + a[3] + a[4] - 3) * 2 + 6;
  }

  sum += a[1] * 2;

  printf("%ld\n", sum/2);

  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include<set>
#include<queue>
#include <iomanip>

typedef long long ll;

#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h, w,m; string s;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}
int main() {
	ll r;
	cin >> r;
	cout << r * r << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using lli = long long int;
using i64 = int64_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

int main() {
  string s;
  cin >> s;
  i64 ans = 1ll << 50;
  for (char c = 'a'; c <= 'z'; ++c) {
    string t = s;
    i64 scr = 0;
    while (true) {
      bool ok = true;
      for (char d : t) if (d != c) ok = false;
      if (ok) break;
      string u(t.size() - 1, '*');
      for (i64 i = 0; i < t.size() - 1; ++i) {
        u[i] = t[i] == c || t[i + 1] == c ? c : t[i];
      }
      t = u;
      ++scr;
    }
    ans = min(ans, scr);
  }
  cout << ans << '\n';
  return 0;
}



Measured memory_bytes: 256
n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])

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

typedef struct _item{
  int wg;  // weight
  long long val; // value
}item;

long long max_value(vector<item> items, int W)
{ 
  int n = items.size();
  vector< vector<long long> > value( n+1, vector<long long>(W+1) );

  for(int i=0; i<=n; i++)
  {
  	for(int w=0; w<=W; w++)
    {
      if( i==0 || w==0)
        value[i][w] = 0;
      
      else if(items[i-1].wg <= w)
        value[i][w] = max( value[i-1][w],
                           items[i-1].val + value[i-1][w - items[i-1].wg]
                          );
      else
        value[i][w] = value[i-1][w];
    }
  }
  
  return value[n][W];
}

int main()
{
  int n, W;
  cin >> n >> W;
  
  vector<item> items(n);
  
  for(int i=0; i<n; i++)
  	cin >> items[i].wg >> items[i].val;
  
  cout << max_value(items, W) << endl;
  
  return 0;
}

Measured memory_bytes: 80256
#include<stdio.h>
 
 
int main()
{
	long n,k,x,y,z,m;
	long i, j;
	scanf("%ld %ld", &n,&k);
	for (i = 0; i < n; i++) {
		if (i == 0) {
			scanf("%ld", &y);
			m = y;
			continue;
		}
		scanf("%ld",&x);
		if (x>m) {
			m = x;
		}
		if (x < y) {
			z = y;
			y = x;
			x = z;
		}
		while (x%y != 0) {
			z = y;
			y = x%y;
			x = z;
		}
	}
	if (k%y == 0&&k<=m) {
		printf("POSSIBLE");
		}else{
		printf("IMPOSSIBLE");
	}
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
#include <algorithm>
//#include <utility>
#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;
//#define all(v) v.begin(),v.end()
//ll mod = 998244353 ;
//long double pie = acos(-1) ;
ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}
const int MAX = 2000000 ;

//宣言するときはstaticをつけて静的変数にするかグローバル変数として宣言
//initのときに関数の種類を決定する（0:sum,1:min,2:max）
class SGT{
public :
	int n = 1;
	ll d ;
	ll num[MAX] ;
	int fan ;

//	指定された関数を実行する
	ll f(ll a,ll b){
		if(fan==0) return a+b ;
		else if(fan==1) return min(a,b) ;
		else if(fan==2) return max(a,b) ;
		else return d ;
	}

	void d_set(int b){
		fan = b ;
		if(fan==0) d = 0 ;
		else if(fan==1) d = INF ;
		else if(fan==2) d = -INF ;
	}

//	初期化する、bは関数の種類を指定する
	void init(vector<ll> &a,int b){
		d_set(b) ;
		while(a.size()>n) n *= 2 ;
		for(int i=0;i<n;i++){
			if(i<a.size()) num[n-1+i] = a.at(i) ;
			else num[n-1+i] = d ;
		}
		for(int i=n-2;i>=0;i--){
			num[i] = f(num[i*2+1],num[i*2+2]) ;
		}
	}

	void init(ll a,ll sz,int b){
		d_set(b) ;
		while(sz>n) n *= 2 ;
		for(int i=0;i<n;i++){
			if(i<sz) num[n-1+i] = a ;
			else num[n-1+i] = d ;
		}
		for(int i=n-2;i>=0;i--){
			num[i] = f(num[i*2+1],num[i*2+2]) ;
		}
	}

//	内容次第でwhile内の計算式を書き換える→書き換えなくて良くなった
	void update(int i,ll a){
		i += n-1 ;
		num[i] = a ;
		while(i>0){
			i = (i-1)/2 ;
			num[i] = f(num[i*2+1],num[i*2+2]) ;
		}
	}

//	最初に呼び出すときは[a,b)だけで十分
	ll query(int a,int b,int l=0,int r=-1,int now=0){
		if(r==-1) r = n ;
		if(r<=a||b<=l) return d ;
		if(a<=l&&r<=b) return num[now] ;
		ll r1 = query(a,b,l,(l+r)/2,now*2+1) ;
		ll r2 = query(a,b,(l+r)/2,r,now*2+2) ;
		return f(r1,r2) ;
	}
};

int main(){
	ll n,k ;
	cin >> n >> k ;
	ll ans = n-k+1 ;
	set<int> s ;
	vll a(n),p={0} ;
	for(auto &i:a) cin >> i ;
	for(int i=1;i<n;i++) if(a.at(i-1)>a.at(i)) p.push_back(i) ;
	p.push_back(n) ;
//	for(auto i:p) cout << i << " " ; cout << endl ;
	for(int i=0;i+1<p.size();i++){
		for(int j=0;j<max(0LL,p.at(i+1)-p.at(i)-k+1);j++) s.insert(p.at(i)+j) ;
	}
//	cout << ans << endl ;
	if(s.size()>1) ans -= s.size()-1 ;
//	cout << ans << endl ;
	static SGT mn,mx ;
	mn.init(a,1) ;
	mx.init(a,2) ;
//	cout << ans << endl ;
	for(int i=0;i+k<n;i++) if(a.at(i)==mn.query(i,i+k)&&a.at(i+k)==mx.query(i+1,i+k+1)&&!s.count(i)) ans-- ;
	cout << ans << endl ;
}


Measured memory_bytes: 22372
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vd(T) vector<vector<T>>
#define v(T) vector<T>
#define mod (ll)(1e9+7)
#define pp(T) pair<T,T>
#define pb push_back
#define mp make_pair
#define NN 100005
#define IO ios_base::sync_with_stdio(NULL),cin.tie(0),cout.tie(0)
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define DEBUG cout<<"***********DEBUGGING***********"<<endl
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; 
ll power(ll a,ll b){ if(b==0) return 1; ll s=power(a,b/2); s*=s;if(b&1) return s*a; return s;}
ll powermod(ll a,ll b,ll m){ if(b==0) return 1; ll s=power(a,b/2);s*=s; s%=m; if(b&1) return (s*a)%m; return s;}
inline int add(ll a,ll b,ll m=0){
    if(m==0) return a+b;
    return (a%m+b%m)%m;
}

inline int sub(ll a,ll b ,ll m=0){
    if(m==0) return a-b;
    return ((a%m-b%m)%m+m)%m;
}

inline int mul(ll a,ll b,ll m=0){
    if(m==0)return (a*b);
    return ((a%m)*(b%m))%m;
}

inline int div(ll a,ll b,ll m=0){
    if(m==0) return a/b;
    return ((a%m)*(powermod(a,b,m-2)%m))%m;
}

bool isopen(char c){
    return ((c=='(')||(c=='{')||(c=='['));
}

ll longest_balanced_parenthesis(string a,ll n){
    stack<char> s;
    ll start=0;
    ll ans=0,m=0;
    for(ll i=0;i<n;i++){
        if(isopen(a[i])){
            s.push(a[i]);
        }
        else{
            if(isopen(a[i])|| s.empty()){
                m=max(m,ans);
                continue;
            }
            else{
                s.pop();
                ans+=2;
                m=max(ans,m);
            }
        }
    }

    return m;

}

ll setup_k(ll *a,ll k){
  ordered_set x;
  // Now , insert and then check number of integers less than k by just using x.order_of_key(k+1)
}



int main() {

    IO; 
	
  	ll a;
  cin>>a;
  char c;
  cin>>c;
  ll b;
  cin>>b;
  if(c=='+')
    cout<<a+b;
  else if(c=='-')
    cout<<a-b;
  else if(c=='*')
    cout<<a*b;
  else
    cout<<a/b;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9;
using namespace std;
using ll = long long;
vector<vector<char>> c(52, vector<char>(52));
int H, W, cnt;
int main() {
	cin >> H >> W;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) cin >> c[i][j];
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (c[i][j] == '#' && c[i][j - 1] != '#' && c[i - 1][j] != '#' && c[i][j + 1] != '#' && c[i + 1][j] != '#') cnt++;
		}
	}
	if (cnt == 0) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


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

#define SZ(x) ((int)(x).size())
#define LEN(x) ((int)(x).length())
using namespace std;

int main() {
	long int a, b, n,ans;
	cin >> a >> b >> n;
	if(n<b){
    	ans=floor(a * n / b) - a * floor(n / b);
    }
  	
	else ans = floor(a * (b-1) / b) - a * floor((b-1) / b);

	cout << ans;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
#define gmul(x,y) x=mul(x,y)
using namespace std;

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

const int N = 1e7 + 5;

int cnt[N];

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	rep(i,2,N){
		for(int j = i;j < N; j += i){
			++cnt[j];
		}
	}
	int n;
	cin >> n;
	ll ans = 0;
	rep(i,1,n+1){
		ans += 1LL * i * (cnt[i]+1);
	}
	cout << ans << '\n';
}


Measured memory_bytes: 42664
from collections import defaultdict
from heapq import heappush, heappop, heapify
from bisect import bisect_left
from itertools import groupby

class Solution:
    def main(self):
        N, K = map(int, input().split())
        S = input()

        counts = [len(list(g)) for k, g in groupby(S)]

        n_thr = len(counts) - 1
        n_thr = max(0, n_thr - 2*K)
        print(N-1-n_thr)


if __name__ == '__main__':
    Solution().main()


Measured memory_bytes: 4348
n = gets.to_i
V = gets.split.map(&:to_i)

even, odd = V.partition.with_index { |_,i| i.even? }

even_count = even.inject(Hash.new{0}) do |hash, e|
  hash[e] += 1
  hash
end

odd_count = odd.inject(Hash.new{0}) do |hash, o|
  hash[o] += 1
  hash
end

sorted_even_count = even_count.sort_by {|k, v| -v}
sorted_odd_count = odd_count.sort_by {|k, v| -v}

# それぞれの最頻値が異なる
if sorted_even_count[0][0] != sorted_odd_count[0][0]
  # それぞれの最頻値に書き換えるのが最適
  puts n - sorted_even_count[0][1] - sorted_odd_count[0][1]
else
  # e を E1 で書き換え、o を O2 で書き換える
  case1 = if sorted_odd_count.size > 1
            n - sorted_even_count[0][1] - sorted_odd_count[1][1]
          else
            n - sorted_even_count[0][1] - 0
          end
  # e を E2 で書き換え、o を O1 で書き換える
  case2 = if sorted_even_count.size > 1
            n - sorted_even_count[1][1] - sorted_odd_count[0][1]
          else
            n - 0 - sorted_odd_count[0][1]
          end
  puts [case1, case2].min
end


Measured memory_bytes: 21264