akhauriyash/Code-Regression huggingface dataset:
s = str(input())
k = int(input())
if len(set(list(s)))==1:
    print((len(s)*k)//2)
    exit()

t = [1]
for i in range(1, len(s)):
    if s[i-1]==s[i]:
        t[-1]+=1
    else:
        t.append(1)

a = 0
for i in t:
    a+=(i//2)*k
if s[0]==s[-1]:
    if t[0]%2==t[-1]%2==1:
        a += k-1

print(a)

Measured memory_bytes: 3064
N = int(input())
Bi = list(map(int, input().split()))
listA = [0 for i in range(N)]
listA[N-1] = Bi[N-2]
gokei = 0
listA[0] = Bi[0]
for j in range(N-2, 0, -1):
    listA[j] = min(Bi[j], Bi[j-1])

for k in listA:
    gokei += k
print(gokei)

Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cstring>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cstdlib>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
typedef long long int ll;
#define forn for(int i=0;i<n;i++) 
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define form for(int j=0;j<m;j++) 
#define fora(i,a,b) for(int i = a; i < (b); i++)
#define pb push_back 
#define mp make_pair 
#define sc second 
#define f first 
#define kek cout<<"\n" 
#define all(v) ((v).begin()), ((v).end()) 
#define pob pop_back() 
const ll MOD = 1e9 + 7;
const int N = 1005;
const ll INF = 1e9;
using namespace std;
int main()
{
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	fast;
	//string al = "abcdefghijklmnopqrstuvwxyz";
	ll n, a, b;
	cin >> n >> a >> b;
	ll k = a + b;
	if (k >= n)
	{
		cout << min(a,n);
		return 0;
	}
	ll d = (n / k)*a;
	ll j = n%k;
	


	cout << d+min(j,a);
	return 0;



}

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

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

using ll = long long;
using K = long double;

const ll B = 1e18;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n;
  cin >> n;
  vector<int> p(n), q(n);
  for (auto& e: p) {
    cin >> e;
    --e;
  }
  REP(i, n) q[p[i]] = i;
  int result = n;
  REP(i, n) {
    int j = i;
    int now = -1;
    while (j < n && q[j] > now) {
      now = q[j];
      ++j;
    }
    result = min(result, i + (n-j));
    i = j-1;
  }
  cout << result << '\n';
}


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

using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 5;
int n;
string s;
ll tmp[MAXN], ans = 0;
int cnt2, cnt5;
ll sum[101][101];
ll a;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        int last = 2;
        a = 0;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == '.') {
                last = j + 1;
                break;
            }
            a = 1ll * a * 10 + 1ll * (s[j] - '0');
        }
        for (int j = last; j < last + 9; j++)
            if (j < s.size())
                a = 1ll * a * 10 + 1ll * (s[j] - '0');
            else
                a = 1ll * a * 10;

        // cout << a << endl;
        cnt2 = 0;
        cnt5 = 0;
        while (a % 2 == 0) {
            cnt2++;
            a /= 2;
        }
        while (a % 5 == 0) {
            cnt5++;
            a /= 5;
        }
        ans += sum[max(0, 18 - cnt2)][max(0, 18 - cnt5)];
        for (int j = 0; j <= min(cnt2, 18); j++)
            for (int k = 0; k <= min(cnt5, 18); k++) sum[j][k]++;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3672
/******************************************
* AUTHOR : Anik Das *
* NICK : sadn1ck *
* INSTITUTION : IIEST Shibpur *
******************************************/
#include <bits/stdc++.h>
using namespace std;
#define lld double
#define ll long long
#define MOD 1000000007

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//ios_base& scientific (ios_base& str);
	lld sum = 0;
	ll n = 0, m = 0;
	cin >> n >> m;
	lld a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum = sum + a[i];
	}
	
	int count = 0;
	for (int j = 0; j < n; j++) {
		if (a[j] >= (sum / (4 * m))) {
			count++;
		}
	}
	if (count >= m) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}


return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<map>
#include<math.h>
#include<queue>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1000000007;
const int mod = 1000000007;
const int INF = 1000000001;
const long long LINF = 1e18;
const int MAX = 510000;

int main() {
	string s, t;
	cin >> s >> t;
	if (s.size() == t.size()) {
		for (int i = 0; i < s.size(); i++) {

			cout << s[i] << t[i];
		}
	}
	else {
		for (int i = 0; i < s.size()-1; i++) {

			cout << s[i] << t[i];
		}
		cout << s[s.size() - 1];
	}
	
//	cout << endl;
		return 0;
}

Measured memory_bytes: 3560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double


int main() {
    ll n,w,val=0;
    cin>>n>>w;
    ll a[n],b[n];
    ld x,y;
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];
    ll dp[n+1][w+1];
    for(int i=0;i<=n;i++) dp[i][0]=0;
    for(int i=0;i<=w;i++) dp[0][i]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=w;j++){
            dp[i][j]=dp[i-1][j];
            if(a[i-1]<=j){
                dp[i][j]=max(dp[i][j],b[i-1]+dp[i-1][j-a[i-1]]);
            }
        }
    }
    cout<<dp[n][w]<<"\n";
}

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

#define ll long long

int main() {
	ll n;
	cin >> n;
	vector<ll> a(n);
	ll i, j;
	ll ans = 0;

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

	for (j = 0; j < n - 1; j++) {
		if (a[j] > a[j + 1]) {
			ans += a[j] - a[j + 1];
			a[j + 1] = a[j];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4720
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define N 200010
ll h,w,n;
namespace uf{
  ll p[N],s[N];
  void init(){
      for(int i=0;i<N;i++)p[i]=i,s[i]=1;
  }  
  ll par(ll x){
      return p[x]=(x==p[x]?x:par(p[x]));
  }
  bool unite(ll a,ll b){
      a=par(a),b=par(b);
      if(a==b){
	  if(s[a]==0)return 0;
	  s[a]--;
      }
      else{
	  if(s[a]+s[b]-1<0)return 0;
	  s[a]+=s[b]-1;
	  p[b]=a;
      }
      return 1;
  }
};
struct edge{
  ll a,b,c;
  edge(ll a,ll b,ll c){
      this->a=a,this->b=b,this->c=c;
  } 
  bool operator<(const edge&key)const{
      return this->c>key.c;
  } 
};
vector<edge> v;
int main(){
  cin>>n>>h>>w;
  for(int i=0;i<n;i++){
      ll a,b,c; cin>>a>>b>>c;
      v.push_back(edge(a,b+1e5,c));
  }
  sort(v.begin(),v.end());
  ll ans=0;
  uf::init();
  for(int i=0;i<n;i++){
      if(uf::unite(v[i].a,v[i].b)){
	  ans+=v[i].c;
      }
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
    int n,k,x,count = 0;

    cin >> n >> k;

    for(int i=0; i<n; i++){
        cin >> x;
        count += min(abs(x),abs(k-x))*2;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
local mfl, mce, mmi = math.floor, math.ceil, math.min
local SegTree = {}
SegTree.updateAll = function(self)
  for i = self.stagenum - 1, 1, -1 do
    for j = 1, self.cnt[i] do
      self.stage[i][j] = self.stage[i + 1][j * 2 - 1] + self.stage[i + 1][j * 2]
    end
  end
end
SegTree.create = function(self, n)
  self.emptyvalue = 0
  local stagenum, mul = 1, 1
  self.cnt, self.stage, self.size = {1}, {{}}, {}
  while mul < n do
    mul, stagenum = mul * 2, stagenum + 1
    self.cnt[stagenum], self.stage[stagenum] = mul, {}
  end
  for i = 1, stagenum do self.size[i] = self.cnt[stagenum + 1 - i] end
  self.stagenum = stagenum
  for i = 1, mul do self.stage[stagenum][i] = 0 end
  self:updateAll()
end
SegTree.getRange = function(self, left, right)
  if left == right then return self.stage[self.stagenum][left] end
  local start_stage = 1
  while right - left + 1 < self.size[start_stage] do
    start_stage = start_stage + 1
  end
  local ret = self.emptyvalue
  local tasks = {{start_stage, left, right}}
  while 0 < #tasks do
    local task = tasks[#tasks]
    table.remove(tasks)
    local stage, l, r = task[1], task[2], task[3]
    if (l - 1) % self.size[stage] ~= 0 then
      local newr = mce((l - 1) / self.size[stage]) * self.size[stage]
      table.insert(tasks, {stage + 1, l, mmi(r, newr)})
      l = newr + 1
    end
    if self.size[stage] <= r + 1 - l then
      local pos = mce(l / self.size[stage])
      ret = ret + self.stage[stage][pos]
      l = l + self.size[stage]
    end
    if l <= r then
      table.insert(tasks, {stage + 1, l, r})
    end
  end
  return ret
end
SegTree.decValue = function(self, idx)
  self.stage[self.stagenum][idx] = self.stage[self.stagenum][idx] - 1
  for i = self.stagenum - 1, 1, -1 do
    local dst = mce(idx / 2)
    local rem = dst * 4 - 1 - idx
    self.stage[i][dst] = self.stage[i + 1][idx] + self.stage[i + 1][rem]
    idx = dst
  end
end
SegTree.inc = function(self, idx)
  self.stage[self.stagenum][idx] = 1 + self.stage[self.stagenum][idx]
end
SegTree.new = function(n)
  local obj = {}
  setmetatable(obj, {__index = SegTree})
  obj:create(n)
  return obj
end

local n, k = io.read("*n", "*n")
local sum, conv = {}, {}
sum[1] = {1, io.read("*n") - k}
for i = 2, n do
  sum[i] = {i, sum[i - 1][2] + io.read("*n") - k}
end
sum[n + 1] = {n + 1, 0}
table.sort(sum, function(x, y) return x[2] < y[2] end)
local sumTypeCount = 1
local sumTypeList = {}
conv[sum[1][2]] = 1
sumTypeList[1] = sum[1][2]
for i = 2, n + 1 do
  if sum[i][2] ~= sumTypeList[sumTypeCount] then
    sumTypeCount = sumTypeCount + 1
    conv[sum[i][2]] = sumTypeCount
    sumTypeList[sumTypeCount] = sum[i][2]
  end
end
table.sort(sum, function(x, y) return x[1] < y[1] end)
local segtree = SegTree.new(sumTypeCount)
for i = 1, n do
  sum[i] = sum[i][2]
  segtree:inc(conv[sum[i]])
end
segtree:updateAll()

local bias = 0
local cnt = 0
for i = 1, n do
  local treeleft = conv[bias]
  if treeleft <= sumTypeCount then
    cnt = cnt + segtree:getRange(treeleft, sumTypeCount)
  end
  segtree:decValue(conv[sum[i]])
  bias = sum[i]
end
print(cnt)


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

int main(){
  int h, w;
  cin >> h >> w;
  int hc = h, wc = w;
  vector<string> mat(h);
  for(int i=0; i<h; i++) cin >> mat[i];
  vector<int> vec(26, 0);
  int four=0, two=0, one=0;
  for(int i=0; i<100; i++){
    if(h!=0 && w!=0){
      if(min(h, w) >= 2){
        four++;
        if(w%2==1) two++;
        four += (w-2)/2;
        if(h%2==1) two++;
        four += (h-2)/2;
        w -= 2;
        h -= 2;
      }else{
        if(h!=1 || w!=1){
          if(h==1){
            if(w%2==1) one++;
            two += w/2;
          }else{
            if(h%2==1) one++;
            two += h/2;
          }
          h=0; w=0;
        }else if (h==1 && w==1){
          one++;
          h=0; w=0;
        }
      }
    }
  }
  for(int i=0; i<hc; i++){
    for(int j=0; j<wc; j++){
      vec[mat[i][j]-'a']++;
    }
  }
  for(int i=0; i<four; i++){
    bool isok = false;
    for(int j=0; j<26; j++){
      if(vec[j] >= 4){
        vec[j] -= 4;
        isok = true;
        break;
      }
    }
    if(!isok){
      cout << "No" << endl;
      return 0;
    }
  }
  for(int i=0; i<two; i++){
    bool isok = false;
    for(int j=0; j<26; j++){
      if(vec[j] >= 2){
        vec[j] -= 2;
        isok = true;
        break;
      }
    }
    if(!isok){
      cout << "No" << endl;
      return 0;
    }
  }
  for(int i=0; i<one; i++){
    bool isok = false;
    for(int j=0; j<26; j++){
      if(vec[j] >= 1){
        vec[j] -= 1;
        isok = true;
        break;
      }
    }
    if(!isok){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}
  
  


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

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

vector<int64_t> fact, seq_inv, fact_inv;

void create_fact_mod(int num){
    fact[0] = 1;
    fact[1] = 1;
    for(int i=2; i<=num; i++){
        fact[i] = fact[i-1] * i % MOD;
    }
}

void create_seq_inv_mod(int num){
    seq_inv[0] = 1;
    seq_inv[1] = 1;
    for(int i=2; i<=num; i++){
        seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
    }
}

void create_fact_inv_mod(int num){
    fact_inv[0] = 1;
    fact_inv[1] = 1;
    for(int i=2; i<=num; i++){
        fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
    }
}

void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int main(){
    int64_t N, M, K;
    cin >> N >> M >> K;
    int64_t A = N*M;

    int64_t ans = 0;
    for(int t=0; t<2; t++){
        int64_t res = 0;
        for(int d=1; d<N; d++) add(res, d*(N-d));
        mul(res, M*M % MOD);
        add(ans, res);
        swap(N, M);
    }
    
    create_mod_tables(A);
    mul(ans, comb_mod(A-2, K-2));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

int mgcd(int a, int b) {
	#ifdef LOCAL
	return gcd(a, b);
	#else 
	return __gcd(a, b);
	#endif
}

void solve() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (d < b) {
		cout << "No\n";
		return;
	}
	if (a < b) {
		cout << "No\n";
		return;
	}
	d %= b;
	if (c >= b) {
		cout << "Yes\n";
		return;
	}
	a %= b;
	int g = mgcd(d, b);
	int p = ((b - 1) / g) * g + a % g;
	while (p > b - 1) {
		p -= g;
	}
	if (abs(b - p) < b - c) {
		cout << "No\n";
		return;
	}
	cout << "Yes\n";
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	
	
	int q;
	cin >> q;
	while (q--) {
		solve();
	}	
}


Measured memory_bytes: 384
#include <stdio.h>
 
class Dice2{
public:
    Dice2(){
        number = new int[6];
        relative = new int[55];
        relative[31] = relative[43] = relative[24] = relative[12] = 0;
        relative[3] = relative[20] = relative[52] = relative[35] = 1;
        relative[1] = relative[40] = relative[54] = relative[15] = 2;
        relative[4] = relative[10] = relative[51] = relative[45] = 3;
        relative[2] = relative[30] = relative[53] = relative[25] = 4;
        relative[21] = relative[42] = relative[34] = relative[13] = 5;
    };
    ~Dice2(){
        delete[] number;
        delete[] relative;
    };
 
    void setNumber(int index,int num){
        number[index] = num;
    };
 
    int returnRight(int top,int front){
        int top_index,front_index;
        for(int i = 0; i < 6; i++){
            if(number[i] == top)
                top_index = i;
            if(number[i] == front)
                front_index = i;
        }
        return number[relative[10*top_index+front_index]];
    }
private:
    int* number;
    int* relative;
};
 
int main(){
    Dice2 dice2;
    int x,q,top,front;
    for(int i = 0; i < 6; i++){
        scanf("%d",&x);
        dice2.setNumber(i,x);
    }
    scanf("%d",&q);
    for(int i = 0; i < q; i++){
        scanf("%d %d",&top,&front);
        printf("%d\n",dice2.returnRight(top,front));
    }
}


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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

signed main()
{
  REP(i,5) {
    int x; cin >> x;
    if (x == 0) {
      cout << i+1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3584
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "{ ";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "}";

    return os;
}

ll pow_mod(ll a, ll p) {
    ll res = 1;
    while(p) {
        if (p & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        p >>= 1;
    }

    return res;
}


ll mod_inv(ll a, ll m) {
    ll b = m, u = 0, v = 1;
    while(a) {
        ll t = b / a;
        swap(b -= t * a, a);
        swap(u -= t * v, v);
    }

    return (u % m + m) % m;
}

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

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#ifdef LOCAL
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

// query_id: {show: 1, insert: 0, delete: -1}
using query = pair<int, ll>; // query_id, value
using event = pair<ll, query>; // time, query

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N, Q;
    cin >> N >> Q;

    vector<event> v;

    REP(i, N) {
        ll s, t, x;
        cin >> s >> t >> x;
        v.pb(event(s-x, query(0, x)));
        v.pb(event(t-x, query(-1, x)));
    }

    REP(i, Q) {
        ll d;
        cin >> d;
        v.pb(event(d, query(1, i))); // i is used to restore the order of Q after sorting.
    }

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

    vector<ll> ans(Q);
    multiset<ll> s;

    REP(i, v.size()) {
        query q = v[i].se;
        int t = q.fi;
        ll v = q.se;

        if (t == 0) { //insert
            s.insert(v);
        } else if (t == -1) { //delete
            s.erase(s.find(v)); // lower_bound?
        } else {
            ans[v] = s.empty() ? -1 : *s.begin();
        }
    }

    REP(i, Q) cout << ans[i] << endl;
    
}


Measured memory_bytes: 28132
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <math.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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

//INT_MAX	2,147,483,647 = 2*1.0e9

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

  vector<int> W(N);
  rep(i, N) cin >> W[i];

  int sA = 0;
  rep(i,N) sA += W[i];

  int sT = 0;
  int answer = 1000000;
  for(int i = 0; i < N; i++){
    sT += W[i];
    answer = min(abs(sA - sT * 2), answer);
  }

  cout << answer << endl;

  return 0;
}



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

int	main()
{
    int N;
    cin >> N;
    vector<int> x_vec(N), y_vec(N);
    for (int i = 0; i < N; ++i)
        cin >> x_vec.at(i) >> y_vec.at(i);
    double sum_dist = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            int dx = x_vec.at(j) - x_vec.at(i);
            int dy = y_vec.at(j) - y_vec.at(i);
            sum_dist += hypot(dx, dy);
        }
    }
    cout << setprecision(10) << 2 * sum_dist / N << endl;
}


Measured memory_bytes: 3744
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pp pair<ll,ll>
#define ppp pair<ll,pp >
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef tree<pp,null_type,less<pp>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=a;i<b;i+=1)
#define sz(v) (ll)(v.size())
#define hell (ll)1000000007
#define slld(x) scanf("%lld",&x)
ll t=1, tt;
const ll N=100005;
inline ll mult(ll x,ll y){x%=hell;y%=hell;return (1LL*x*y)%hell;}
inline ll add(ll x,ll y){x+=y;return x%hell;}
inline ll powMod(ll base,ll expo){
	if(base==0)return 0;
	ll ans=1;
	while(expo){
		if(expo&1)ans=mult(ans,base);
		base=mult(base,base); 
		expo>>=1;
	}
	return ans;
}
void solve(){
	ll n;
	cin>>n;
	ld dp[2][3005];
	vector<ld> v(n+1);
	rep(i,1,n+1)
		cin>>v[i];
	dp[0][0]=(ld)(1.0);
	rep(i,1,n+1){
		ll x=i&1;
		rep(j,0,i+1)dp[x][j]=0;
		rep(j,0,i){
			dp[x][j+1]+=dp[x^1][j]*v[i];
			dp[x][j]+=dp[x^1][j]*(1.0-v[i]);
		}
	}
	ld ans=0;
	rep(i,1,n+1){
		if(n-i<i)ans+=dp[n&1][i];
	}
	cout<<fixed<<setprecision(10)<<ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   	//cin>>t;
   	tt=t;
    while(t--){
        solve();
        if(t)cout<<"\n";
    }
    return 0 ;
}


Measured memory_bytes: 384
import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	
	public Main() {
		FastScanner scanner = new FastScanner();
		int N = scanner.nextInt();
		
		long[][] IN = new long[N][2];
		TreeMap<Long, long[]> XPY = new TreeMap<>();
		TreeMap<Long, long[]> XMY = new TreeMap<>();
		for (int i = 0; i < N; i++) {
			long x = scanner.nextLong();
			long y = scanner.nextLong();
			
			IN[i][0] = x;
			IN[i][1] = y;
			
			long [] t = new long[]{x,y};
			XPY.put(x+y, t);
			XMY.put(x-y, t);
		}
		
		long[] A = XPY.firstEntry().getValue();
		long[] B = XPY.lastEntry().getValue();
		long[] C = XMY.firstEntry().getValue();
		long[] D = XMY.lastEntry().getValue();
		
		long Ans = Long.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			Ans = Math.max(Ans, d(IN[i], A));
			Ans = Math.max(Ans, d(IN[i], B));
			Ans = Math.max(Ans, d(IN[i], C));
			Ans = Math.max(Ans, d(IN[i], D));
		}
		
		System.out.println(Ans);
	}
	
	long d(long[] a, long[] b) {
		return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
	}
	
	public static void main(String[] args) {
		new Main();
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	
	private int readByte() {
		if (hasNextByte()) return buffer[ptr++];
		else return -1;
	}
	
	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}
	
	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
		return hasNextByte();
	}
	
	public String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	public long nextLong() {
		if (!hasNext()) throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) nl;
	}
	
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 97652
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

A_c = Counter(A)

A_c_c = 0
for i in A_c.values():
    A_c_c += i*(i-1)//2

for k in range(N):
    ans = A_c_c - (A_c[A[k]] - 1)
    print(ans)


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef map<int, int> mpii;
typedef set<int> seti;

const int mxN = 2e5, iinf = 1e9 + 10, inf = 1e18 + iinf + 10, mod = 1000000007;
const ld pi = 4.0 * atanl(1.0), prec = .000001;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(c) c.begin(), c.end()
#define rall(c) c.end(), c.begin()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

int n, m, t, a[mxN];

void fast() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); }

int main() {
  fast();
  cin >> n >> m;
  FOR(i, 0, m + 2) { cout << "#"; }

  cout << "\n";
  FOR(i, 0, n) {
    string s;
    cin >> s;
    cout << "#" << s << "#"
         << "\n";
  }
  FOR(i, 0, m + 2) { cout << "#"; }

  return 0;
}



Measured memory_bytes: 3564
#include <stdio.h>
#include <string.h>

int main(int argc, const char * argv[]) {
    int slen,i,j;
    char s[100];
    
    while(gets(s)!=NULL){
        slen=(int)strlen(s);
        for(j=0;j<26;j++){
            for(i=0;i<slen;i++){
                
                if('a'<=s[i]&&s[i]<='z')
                    s[i]=s[i]+1;
                if(s[i]=='z'+1)
                    s[i]='a';
            }
            if(strstr(s,"the")!=NULL||strstr(s,"this")!=NULL||strstr(s,"that")!=NULL){
                printf("%s\n",s);
            }
        }
    }
    
    
    
    return 0;
}

Measured memory_bytes: 520
/*بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
const int mx=1e5+5;
const int MOD=1e9+7;
int cnt[mx];
int main ()
{
    int i,n,maxi=0;

    scanf ("%d",&n);
    for (i=0;i<n;i++) {
        int x;
        scanf ("%d",&x);
        maxi=max(maxi,x);
        cnt[x]++;
    }
    int tmp=0,ans=0;
    for (i=1;i<=maxi;i++) if (cnt[i]) {
        ++ans;
        if (cnt[i]%2==0) ++tmp;
    }
    if  (tmp%2==1) --ans;
    printf("%d\n",ans);

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//template<typename key, typename val>
//using ordered_tree =
//  tree<key, val, greater<>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int64;
typedef complex<double> comp;
const double pi = 3.14159265358979323846;
const int inf = (int)1e+9 + 2;
const int64 inf64 = (int64)1e+18 + 2;
const double dinf = 1e+20;
const int mod = 1'000'000'007;//998244353;
const int base = 2187;
const double eps = 1e-8;
const int N = 100'000;
const int LOGN = 19;

int n, m, k;

void solve(int test)
{
  int a, b, c;
  cin >> a >> b >> c;
  cout << max(0, c - a + b) << '\n';
}

void precalc()
{
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  precalc();
  int test = 1;
  //cin >> test;
  //auto start = chrono::high_resolution_clock::now();
  for (int i = 1; i <= test; ++i)
    solve(i);
  //cerr << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << '\n';
  return 0;
}


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

typedef pair<int,int> P;
#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
int dp[13][100010];
int main()
{
    vector<int> devider;
    int temp9, temp6;
    temp9 = 1;temp6 = 1;
    devider.push_back(temp9);
    for (int i = 0; i < 9; i++)
    {
        temp9*=9;
        temp6*= 6;
        if (temp9<100010)
        {
            devider.push_back(temp9);
        }
        if (temp6 < 100010)
        {
            devider.push_back(temp6);
        }
    }
    sort(devider.begin(),devider.end());
    int n;
    cin >> n;
    for (int  i= 0; i < 13; i++)
    {
        for (int j = 0; j < 100010; j++)
        {
            dp[i][j] = INF;
        }
        
    }
    /*for (int i = 0; i < 13; i++)
    {
        dp[i][0] = 0;
    }*/
    dp[0][0] = 0;
    
    
    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < n+1; j++)
        {
            chmin(dp[i+1][j], dp[i][j]);
            if (j-devider[i]>=0)
            {
                chmin(dp[i + 1][j], dp[i + 1][j - devider[i]] + 1);
            }
        }
    }
    cout << dp[12][n] << endl;
    
    
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0;i < (int)(n);i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n);i++)
#define ALL(vec)  (vec).begin(),(vec).end()
#define lli long long int
#define pi 3.1415926535897932384626433832795
#define MAX_INF 9223372036854775807
#define MIN_INF 9223372036854775807+1

int main() {
  long long int ans = 1;
  int N;
  cin >> N;
  vector<int> A(N);
  int m = 0;
  rep(i, N){
  cin >> A[i];
      m = max(m, A[i]) ;
    if(i ==0 && A[i] != 0){
    cout << 0 << endl;
    return 0;
    }
  }
  m++;
  sort(ALL(A));
  if(A[0]==A[1]){
    cout << 0 << endl;
    return 0;
  }
  vector<int> C(m);
  int keep = 0;
  rep(i, N){
    if(keep == A[i]){
      C[keep]++;
    }
    else if(A[i]== keep+1){
    keep++;
      C[keep]++;
    }
    else{
      cout << 0 << endl;
    return 0;
    }
  }
  rep2(i, 1, m){
    rep(j, C[i]){
    ans *= C[i-1];
      ans %= 998244353;
    }
  }
  
      ans %= 998244353;
      ans %= 998244353;
  cout << ans << endl;
}

Measured memory_bytes: 1024
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
const int N = 2e5 + 12;
const int mod = 998244353;
char s[N];int len,g,f[N][3][3][2];
bool same(){for(int i = 2;i <= len;i++)if(s[i] != s[i - 1])return false;return true;}
bool notsame(){for(int i = 2;i <= len;i++)if(s[i] == s[i - 1])return false;return true;}
int main()
{
     scanf("%s",s + 1);len = strlen(s + 1);
     if(same())puts("1");
     else if(len <= 3)
     {
     	if(len == 2){puts("2");}
     	else 
     	{
     		if(s[1] != s[2] && s[1] != s[3] && s[2] != s[3])puts("3");
     		else if(s[1] == s[3])puts("7");
     		else puts("6");
     	}
     }
     else 
     {
     	for(int i = 1;i <= len;i++)g = (g + s[i] - 'a') % 3;
     	for(int i = 0;i < 3;i++)f[1][i][i][0] = 1;
     	for(int i = 1;i < len;i++)
     	 for(int j = 0;j < 3;j++)
     	  for(int k = 0;k < 3;k++)
     	   for(int l = 0;l < 2;l++)
     	    for(int t = 0;t < 3;t++)
     	    (f[i + 1][t][(k + t) % 3][l | (t == j)] += f[i][j][k][l]) %= mod;
     	int ret = ((f[len][0][g][1] + f[len][1][g][1]) % mod + f[len][2][g][1]) % mod;
     	printf("%d\n",(ret + notsame()) % mod);
     }
}

Measured memory_bytes: 14464
#include <bits/stdc++.h>
#define ll int64_t
#include <cstdlib> 
#include <math.h>
#include<cstdio>
#include<cstring>
#define FOR(I, A, B) for (ll I = (A); I <= (B); I++)
#define fo(i,n) for(ll i=0;i<n;i++)
#define sz(a) ll((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define dbg(x) cout << #x << " = " << x << endl
#define dbg2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define dbg3(x,y,z) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
#define dbg4(x,y,z,q) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #q << " = " << q << endl
#define scan(char_array) scanf("%[^\n]s",&char_array)
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
struct three{
ll a,b,c;

};
ll n,m;
ll aans;
vector<three> our;
void fu(ll x,ll y ,ll z){
 //ll ans=0;
 vector<ll> v;
 for(auto kk:our){
  ll t=(x)*(kk.a)+(y)*(kk.b)+(z)*(kk.c);
   v.pb(t);

    }
    sort(all(v));
	reverse(all(v));
	ll tt=0;
	fo(i,m){
		tt+=v[i];

	}
	


aans=max(aans,tt);


}

int main(){

cin>>n>>m;
aans=0;

fo(i,n){
	three tmp;
	cin>>tmp.a>>tmp.b>>tmp.c;
	our.pb(tmp);


}
fu(1,1,1);
fu(1,1,-1);
fu(1,-1,1);
fu(1,-1,-1);
fu(-1,1,1);
fu(-1,1,-1);
fu(-1,-1,1);
fu(-1,-1,-1);
cout<<aans<<endl;


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define pb push_back 
#define N 410
using namespace std;
ll dp[N][N], pref[N], A[N];
ll fun(int a, int b){
	if(a == b)
		return 0;
	if(dp[a][b] != -1)
		return dp[a][b];
	ll mini = 1e18;
	for(int i = a; i <= b - 1; i++){
		mini = min(mini, pref[i] - pref[a - 1] + pref[b] - pref[i] + fun(a, i) + fun(i + 1, b));
	}
	return dp[a][b] = mini;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> A[i];
	for(int i = 1; i <= n; i++){
		pref[i] = A[i] + pref[i - 1];
	}
	memset(dp, -1, sizeof(dp));
	cout << fun(1, n) << '\n';

}

Measured memory_bytes: 1664
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let x:usize = read();
    let y:usize = read();
    let mut ans = "No";
    for i in 0..=x {
        for j in 0..=x {
            if i + j == x {
                if i * 2 + j * 4 == y {
                    ans = "Yes";
                    break;
                }
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2156
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const char* T="CODEFESTIVAL2016";
char S[30];

int main() {
	scanf("%s",S);
	int ans=0;
	for(int i=0;T[i];i++)
		if(T[i]!=S[i])
			ans++;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
n, m, *L = map(int, open(0).read().split())
con = [[] for _ in range(n)]
for s, t in zip(*[iter(L)] * 2):
	con[s - 1] += t - 1,
	con[t - 1] += s - 1,

# 辺を取り出して木をつくる
tree = [[] for _ in range(n)]
lev = [0] * n
vis = [False] * n
vis[0] = True
reserve = set()
q = [0]
while q:
	cur = q.pop()
	for nxt in con[cur]:
		if vis[nxt]:
			continue
		reserve.add((cur, nxt))
		tree[cur] += nxt,
		tree[nxt] += cur,
		lev[cur] += 1
		lev[nxt] += 1
		vis[nxt] = True
		q += nxt,

# 　要らない辺を適当に方向付ける
ans = []
deg = [0] * n
for s, t in zip(*[iter(L)] * 2):
	if (s - 1, t - 1) not in reserve and (t - 1, s - 1) not in reserve:
		ans += "{} {}".format(s, t),
		deg[s - 1] ^= 1

# 葉から順に辺の方向を決定
from collections import deque
q = deque()
done = [False] * n
for i, l in enumerate(lev):
	if l == 1:
		q.append(i)
while q:
	cur = q.popleft()
	for nxt in tree[cur]:
		if done[nxt]:
			continue
		if deg[cur]:
			ans += "{} {}".format(cur + 1, nxt + 1),
			deg[cur] ^= 1
		else:
			ans += "{} {}".format(nxt + 1, cur + 1),
			deg[nxt] ^= 1
		done[cur] = True
		lev[nxt] -= 1
		if lev[nxt] == 1:
			q.append(nxt)

if any(deg):
	print(-1)
else:
	print("\n".join(ans))


Measured memory_bytes: 65876
n,a,b = gets.split.map &:to_i
if a != 0 
	split = (n / (a+b))
	ret = split*a
	modulo = n % (a+b)
	if modulo <= a
		ret += modulo
	else
		ret += a
	end
	puts ret
else
	puts 0
end

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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> VECLL;
typedef vector<P> VECP;
typedef priority_queue<P,VECP,greater<P> > PQP;
typedef priority_queue<ll, VECLL, greater<ll> > PQll;

#define rep(i,a,n) for(ll i = a;i < n;i++)   
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second


int main(){
    string s;
    cin >> s;
    rep(i,0,3) cout << s[i];
    cout << endl;
    return 0;
}

Measured memory_bytes: 3612
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/
 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
 
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<int, II> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
 
const ll MODBASE = 1000000007LL;
const int MAXN = 100010;
const int MAXM = 30010;
const int MAXK = 16;
const int MAXQ = 200010;

int n, m, dp[MAXN];
string s;
deque<II> window;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    cin >> s;
    dp[n] = 0;
    window.push_back(II(dp[n], n));
    FORE(i,n-1,0) {
        while (window.front().SE > i + m) window.pop_front();
        if (s[i] == '1') dp[i] = 1000000000;
        else {
            if (window.front().FI == 1000000000) {
                cout << -1;
                return 0;
            } 
            dp[i] = window.front().FI + 1;
        }

        while (!window.empty() && window.back().FI >= dp[i]) window.pop_back();
        window.push_back(II(dp[i], i));
    }

    // FOR(i,0,n) cout << i << ' ' << dp[i] << "\n";

    int now = 0;
    while (now < n) {
        int nex = -1;
        FOR(i,now+1,n) {
            if (dp[i] == dp[now] - 1) {
                nex = i;
                break;
            }
        }
        cout << nex - now << ' ';
        now = nex;
    }
    return 0;
}


Measured memory_bytes: 1104
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;

bool BinarySearch(int A[], int key, int size)
{
    int left = 0;
    int right = size;
    while (left < right)
    {
        int middle = (left + right) / 2;
        if (A[middle] == key)
        {
            return true;
        }
        else if (A[middle] < key)
        {
            left = middle + 1;
        }
        else if (key < A[middle])
        {
            right = middle;
        }
    }
    return false;
}

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

    int n;
    int A[100001];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    
    int m, key, sum = 0;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> key;
        if (BinarySearch(A, key, n))
            sum++;
    }
    cout << sum << endl;
}



Measured memory_bytes: 3468
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a;
    cin>>a;
    int cnt=0;  //用来标记
    for(int i=0;i<a.size();i++){
        if(a[i]=='C'){
            cnt=1;
        }
        if(a[i]=='F'&&cnt==1){
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

N,M,S=map(int,input().split())
pro=Dijkstra(N*(50*(N-1)+1))
for i in range(0,M):
    u,v,a,b=map(int,input().split())
    for j in range(a,50*(N-1)+1):
        pro.add(N*j+u-1,N*(j-a)+v-1,b)
        pro.add(N*j+v-1,N*(j-a)+u-1,b)

for i in range(0,N):
    c,d=map(int,input().split())
    for j in range(0,50*(N-1)):
        to=min(50*(N-1),j+c)
        pro.add(N*j+i,N*to+i,d)

S=min(50*(N-1),S)
ans=pro.shortest_path(N*S)
for i in range(1,N):
    p=float("inf")
    for j in range(0,50*(N-1)+1):
        p=min(p,ans[N*j+i])
    print(p)


Measured memory_bytes: 158144
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    CNTR = 0
    CNTG = 0
    CNTB = 0
    for i in range(N):
        if S[i] == 'R':
            CNTR += 1
        if S[i] == 'G':
            CNTG += 1
        if S[i] == 'B':
            CNTB += 1
    CONB = CNTR * CNTG * CNTB
    CNT = 0
    for i in range(N):
        for j in range(i,N):
            if S[j] != S[i]:
                k = j + (j-i)
                if k > N-1:
                    continue
                if S[k] != S[i] and S[k] != S[j]:
                    CNT += 1
    print(CONB - CNT)


if __name__ == '__main__':
    main()

Measured memory_bytes: 73660
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,-1,0,0,1,1,-1,-1};
vector<ll>dy={0,0,1,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>&p){
  return os << p.first << " " << p.second;
}
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n,q;cin>>n>>q;
  vector<ll>a(q+1,n);
  rep(i,0,q)cin>>a[i+1];
  stack<ll>st;
  rep(i,0,q+1){
    while(!st.empty()&&st.top()>=a[i])st.pop();
    st.push(a[i]);
  }
  a.clear();
  while(!st.empty()){
    a.PB(st.top());
    st.pop();
  }
  reverse(ALL(a));
  q=a.size();
  vector<ll>ret(n);
  vector<ll>dp(q);
  dp[q-1]=1;
  rrep(i,0,q){
    ll now=a[i];
    while(now){
      ll idx=upper_bound(a.begin(),a.begin()+i,now)-a.begin()-1;
      if(idx<0){
        ret[now-1]+=dp[i];
        break;
      }
      dp[idx]+=now/a[idx]*dp[i];
      now%=a[idx];
    }
  }
  //debug(a,q);
  //debug(dp,q);
  //debug(ret,n);
  //ret[n-1]+=dp[0];
  rrep(i,0,n-1)ret[i]+=ret[i+1];
  rep(i,0,n)cout<<ret[i]<<endl;
  return 0;
}

Measured memory_bytes: 4636
S=input()

for i in range(len(S)-1):
  if S[i]==S[i+1]:
    print(i+1,i+2)
    exit()
for i in range(len(S)-2):
  if S[i]==S[i+2]:
    print(i+1,i+3)
    exit()
print(-1,-1)

Measured memory_bytes: 3188
X = int(input())
if X <= 599:
    print('8')
elif X <= 799:
    print('7')
elif X <= 999:
    print('6')
elif X <= 1199:
    print('5')
elif X <= 1399:
    print('4')
elif X <= 1599:
    print('3')
elif X <= 1799:
    print('2')
else:
    print('1')

Measured memory_bytes: 9172