akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>
#include <tuple>

using namespace std;

int dist(int n, int x, int y, int u, int v) {
    // if (u == v) return 0;
    // if (u > v) return dist(n, x, y, v, u);
    // guarantee u < v
    int d = v - u;
    int dd = abs(x - u) + 1 + abs(y - v);
    return min(d, dd);
}

map<int, int> dis_count;

void precompute(int n, int x, int y) {
    for (int u = 0; u < n; u++) {
        for (int v = u + 1; v < n; v++) {
            dis_count[dist(n, x, y, u, v)]++;
        }
    }
}

int solve(int n, int x, int y, int k) {
    return dis_count[k];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, x, y;
    cin >> n >> x >> y;
    x--;
    y--;
    precompute(n, x, y);
    for (int k = 1; k < n; k++) {
        cout << solve(n, x, y, k) << endl;
    }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (ll(i) = 0; (i) < (n); (i)++)
#define all(x) (x).begin(), (x).end()
#define print(x) cout << (x) << endl;

typedef long long ll;
const ll INF = 99999999999999;
const ll MOD = 1000000007;

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
ll lcm(ll number1, ll number2)
{
    return number1 * number2 / gcd(number1, number2);
}
template <class T>
bool contain(const std::string &s, const T &v)
{
    // contain(to_string(N), '3')
    return s.find(v) != std::string::npos;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
        return c - '0';
    return 0;
}
using namespace std;

int main()
{
    ll n, k, s;
    cin >> n >> k >> s;
    if (s == 1000000000)
    {
        rep(i, k)
        {
            cout << 1000000000 << " ";
        }
        rep(i, n - k)
        {
            cout << 999999999 << " ";
        }
    }
    else
    {
        rep(i, k)
        {
            cout << s << " ";
        }
        rep(i, n - k)
        {
            cout << 1000000000 << " ";
        }
    }

    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define LL long long
#define LD long double
#define VI vector<int>
#define VPII vector<PII>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define pb pop_back
#define FOR(a,s,d) for (int a = (s); a <= (int)(d); ++a)
#define FORD(a,s,d) for (int a = (s); a >= (int)(d); --a)
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define ALL(x) x.begin(), x.end()
#define siz(x) ((int)x.size())
#define Sim template <class s
Sim, class d> ostream & operator<<(ostream &os, pair<s,d> x){return os << "<" << x.f << ", " <<
  x.s << "> ";}
Sim> auto operator<<(ostream &os, s x) -> typename enable_if<!is_same<s,string>::value,
  decltype(x.begin(), os)>::type
{ int o = 0; os << "{"; for (auto c : x) {if(o++) os << ", "; os << c;}return os << "} ";}
void dor() {cerr << endl;}
Sim, class ...t> void dor(s x, t...y) {cerr << x << " "; dor(y...);}
#ifdef DEB
#define debug(c...) dor(__FUNCTION__, ":", __LINE__, ": ", c)
#else
#define debug(...)
#endif
const LL mod = 998244353;
const int M = 1024 * 256;

string s;
int sum, n;
LL res;

void brute()
{
  set<string> S;
  queue<string> Q;
  Q.push(s);
  S.insert(s);
  while (!Q.empty())
  {
    string x = Q.front();
    Q.pop();
    for (int i = 1; i < siz(x); i++)
    {
      if (x[i - 1] != x[i])
      {
        string xx = x;
        char c = (char)((2 * ((int)x[i - 1] + (int)x[i] - 2 * (int)'a')) % 3 + (int)'a');
        xx[i - 1] = c;
        xx[i] = c;
        if (S.find(xx) == S.end())
        {
          S.insert(xx);
          Q.push(xx);
        }
      }
    }
  }
  printf("%d\n", siz(S));
}

LL dp[M][3][3][2];

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> s;
  n = siz(s);
  LL diff = 0;
  bool ok = false;
  for (int i = 0; i < n; i++)
  {
    if (i > 0 && s[i - 1] != s[i])
    {
      diff++;
      ok = true;
    }
    sum += s[i] - 'a';
  }
  sum %= 3;
  if (!ok)
  {
    printf("1\n");
    return 0;
  }
  
  if (n < 5)
  {
    brute();
    return 0;
  }
  
  dp[0][0][0][0] = 1;
  dp[0][1][1][0] = 1;
  dp[0][2][2][0] = 1;
  
  for (int i = 1; i < n; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      for (int k = 0; k < 3; k++)
      {
        for (int l = 0; l < 3; l++)
        {
          if (k != l)
          {
            dp[i][j][k][0] += dp[i - 1][(j - k + 3) % 3][l][0];
          }
          else
          {
            dp[i][j][k][1] += dp[i - 1][(j - k + 3) % 3][l][0];
          }
          dp[i][j][k][1] += dp[i - 1][(j - k + 3) % 3][l][1];
        }
        dp[i][j][k][0] %= mod;
        dp[i][j][k][1] %= mod;
      }
    }
  }
  printf("%lld\n", (dp[n - 1][sum][0][1] + dp[n - 1][sum][1][1] + dp[n - 1][sum][2][1] + (diff == n - 1)) % mod);
  return 0;
}

Measured memory_bytes: 29264
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    long long a,b;
    scanf("%lld%lld",&a,&b);
    if(a==1)
        printf("%lld\n",abs(b-2));
    else
    {
        long long sum;
        sum=a*b-a*2-b*2+4;
        printf("%lld\n",abs(sum));
    }
    return 0;
}

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

#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define ALL(v) v.begin(), v.end()
#define SZ(x) ((ll)(x).size())

const double PI  = acos(-1.0);
const double EPS = 1e-9;
const int INF = 1e9+10;
const ll mod = 998244353;
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; }
#define print(x) cerr << #x << " is " << x << endl;
//#define print(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 
ll A[100005], NODE[100005], ARC[100005], S[100005];
int main()
{
    ll N, ans = 1;
    cin >> N;
    rep(i, N + 1)cin >> A[i];
    S[N] = A[N];
    for (int i = N - 1; i>= 0; i--)S[i] = S[i+1] + A[i];
    //rep(i, N + 1)fprintf(stderr, "%d\n", S[i]);
    //exit(1);
    //N = 60;
    //ll tmp = 1;
    //rep(i, N)tmp *= 2, A[i] = 0;
    //A[N] = tmp;
    

    if (A[0] > 0){
        if (N == 0 && A[0] == 1)cout << 1;
        else cout << -1;
        return 0;
    }
    NODE[0] = 1;
    ARC[0] = 1;
    reps(i, 1, N + 1){
        NODE[i] = ARC[i - 1] * 2;
        chmin(NODE[i], S[i]);
        ARC[i] = NODE[i] - A[i];
        if (ARC[i] < 0){
            cout << -1;
            return 0;
        }
        
        ans += NODE[i];
        //fprintf(stderr, "%d: %d, %d %d\n", i, NODE[i], ARC[i], ans);
    }
    cout << ans;
    return 0;
    ll res = ARC[N];
    for (int i = N - 1; i >= 0; i--){
        ll cnt = min(ARC[i], res);
        ans -= (N - i) * cnt;
        res -= cnt;
        if (res == 0)break;
    }
    if (res == 0)cout << ans;
    else cout << -1;
    return 0;
}


Measured memory_bytes: 6760
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<map>
using namespace std;
#define ll long long
int main(){
    ll n,v;
    cin >>n;
    map <ll,ll> vmapodd;
    map <ll,ll> vmapevl;
    ll i;
    int oddflg=0;
    for(i=0;i<n;i++){
      cin >>v;
      if(oddflg==0){
      auto itr = vmapodd.find(v);
      if(itr != vmapodd.end()){
        vmapodd[v]+=1;
      }else{
        vmapodd[v]=1;
      }
    }else{
      auto itr = vmapevl.find(v);
      if(itr != vmapevl.end()){
        vmapevl[v]+=1;
      }else{
        vmapevl[v]=1;
      }
    }
    oddflg=(oddflg+1)%2;
  }
    ll odd =0;
    ll oddkey=0;
    ll oddmax=0;
    ll oddsec=0;
    ll evlmax=0;
    ll evlsec=0;
    ll evlkey=0;
    for(auto it=vmapodd.begin();it!=vmapodd.end();++it){
        if(it->second>=oddmax){
          oddsec=oddmax;
          oddmax=it->second;
          oddkey=it->first;
        } else if(it->second>=oddsec){
          oddsec=it->second;
        }
      }
      for(auto it=vmapevl.begin();it!=vmapevl.end();++it){
          if(it->second>=evlmax){
            evlsec=evlmax;
            evlmax=it->second;
            evlkey=it->first;
          } else if(it->second>=evlsec){
            evlsec=it->second;
          }
        }
    ll ans;
    if(oddkey!=evlkey){
      ans=n-oddmax-evlmax;
    }else{
      ll a=oddmax+evlsec;
      if(oddsec+evlmax>=a){
        a=oddsec+evlmax;
      }
      ans=n-a;
    }
    cout << ans;
    return 0;
}


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

N, K = MAP()
S = input()

point = 0

# default
for i in range(N-1):
    if S[i] == S[i+1]:
        point += 1


ans = min(N-1, point + 2 * K)
print(ans)



Measured memory_bytes: 5464
#include<stdio.h>

int main(void){
	char s1, s2, s3;
	int ct = 0;
	scanf("%c%c%c", &s1, &s2, &s3);
	if (s1 == '1') ct++;
	if (s2 == '1') ct++;
	if (s3 == '1') ct++;
	printf("%d", ct);
}

Measured memory_bytes: 128
using System;

namespace ITP1_4_B {
    class Program {
        static void Main(string[] args) {
            double d = double.Parse(Console.ReadLine());
            double a = d * d * Math.PI;
            double b = (d + d) * Math.PI;
            Console.WriteLine("{0} {1}", a, b);
        }
    }
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int k,n; cin >> n >> k;
    vector<int> p(n); rep(i,n) cin >> p[i];
    vector<double> e(n);
    rep(i,n){
        if(p[i]%2 == 0) e[i] = double(p[i]/2 + 0.5);
        else e[i] = double(p[i]/2 + 1.0);
    }
    vector<double> esum(n+1,0);
    rep(i,n) esum[i+1] = esum[i] + e[i];
    double ans = 0.0;
    for(int i = 0; i+k <= n; ++i){
        ans = max(ans, esum[i+k]-esum[i]);
    }
    cout << fixed << setprecision(8) << ans << endl;
}


Measured memory_bytes: 4224
def dynamic_programming(N):
    mod = 10 ** 9 + 7
    dp = [{} for _ in range(N+1)] 
    dp[0]['TTT'] = 1
    for n in range(N):
        for last3 in dp[n].keys():
            for c in 'ACTG':
                if is_ok(last3 + c):
                    if last3[1:] + c in dp[n+1].keys():
                        dp[n+1][last3[1:] + c] += dp[n][last3] % mod
                    else:
                        dp[n+1][last3[1:] + c] = dp[n][last3] % mod
    ret = sum(dp[N].values()) % mod
    return ret

def is_ok(last4):
        
    for i in range(4):
        t = list(last4)
        if i < 3:
            t[i], t[i+1] = t[i+1], t[i]
        if ''.join(t).count('AGC') > 0:
            return False
    return True

def main():

    n = int(input())
    #solver = DP(n)

    #print(solver.dp(0, 'CCC'))
    print(dynamic_programming(n))


main()

Measured memory_bytes: 3828
N, K = map(int, input().split())
S = input()

cnt = 0
for i in range(N-1):
    if S[i:i+1]!=S[i+1:i+2]:
        cnt += 1

if cnt//2 + 1 <= K:
    print(N-1)
else:
    print((N-1) - cnt + 2*K)


Measured memory_bytes: 3316
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int MOD = 1_000_000_007;
        int a[] = new int[m];
        int dp[] = new int[n + 2];
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            a[i] = Integer.parseInt(sc.next());
            dp[a[i]] = -1;
        }
        sc.close();
        for (int i = 0; i < n; i++) {
            if (dp[i] == -1) {
                continue;
            }
            if (dp[i + 1] != -1) {
                dp[i + 1] += dp[i];
                dp[i + 1] %= MOD;
            }
            if (dp[i + 2] != -1) {
                dp[i + 2] += dp[i];
                dp[i + 2] %= MOD;
            }
        }
        System.out.print(dp[n]);
    }
}

Measured memory_bytes: 44684
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int n,k;
  cin>>n>>k;
  std::vector<int> p(n);
  for(int i=0;i<n;i++){
    cin>>p[i];
  }

  std::set<int> range_value;
  std::unordered_multiset<int> pos;
  for(int i=0;i<k;i++){
    range_value.insert(p[i]);
  }
  int result=1;
  pos.insert(k-1);
  for(int i=k;i<n;i++){
    int curr_min=*range_value.begin();
    int curr_max=*(--range_value.end());
    int next_value=p[i];
    range_value.insert(next_value);
    range_value.erase(p[i-k]);
    if(curr_min<*range_value.begin()&&curr_max<*(--range_value.end())){
      //nothing
    }else{
      pos.insert(i);
      result++;
    }
  }


  int increasing_pos_count=0;
  int max=-1;
  int increasing_length=0;
  for(int i=0;i<n;i++){
    if(max<p[i]){
      increasing_length++;
      max=p[i];
      if(pos.find(i)!=pos.end()&&increasing_length>=k){
        increasing_pos_count++;
      }
    }else{
      increasing_length=1;
      max=p[i];
    }
  }

  if(increasing_pos_count>=2){
    result-=(increasing_pos_count);
    result++;
  }


  assert(result>=1);



  cout<<result<<endl;

  return 0;
}

Measured memory_bytes: 10368
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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, M, K = MAP()

def C(n, r):
	return (((factorial[n] * power(factorial[r], MOD-2) % MOD) * power(factorial[n-r], MOD-2)) % MOD)

def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % MOD
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % MOD
	else:
		return power(x, int((y-1)/2)) ** 2 * x % MOD

factorial = [1]
for n in range(1, 2*10**5+1):
    factorial.append(factorial[n-1]*n%MOD)

pat = C(N*M-2, K-2)

X = 0
for d in range(1, M):
	X = (X + (d*(M-d)*(N*N)))%MOD

Y = 0
for d in range(1, N):
	Y = (Y + (d*(N-d)*(M*M)))%MOD

print(pat*(X+Y)%MOD)


Measured memory_bytes: 11764
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll mod=1e9+7;
ll inf=1e18;

/*
ac
*/

int main(void){
	ll n,k,a,b,ans=0;
	cin>>n>>k;
	a=n/k;
	ans+=a*a*a;
	if(k%2==0){
		b=a;
		if(k*a+k/2<=n)b++;
		ans+=b*b*b;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

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

#define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(0, 1); \
                 auto rnd = bind(__dis, __gen);

const int INF = 1E18;
const int mod = 1E9 + 7;

int32_t main() {
    fastIO();
    
    int n, x, tmp, minCost = INF;
    cin >> n >> x;
    
    for (int i = 0; i < n; ++i) cin >> tmp, x -= tmp, minCost = min(minCost, tmp);
    
    cout << n + x / minCost << "\n";
    
    return 0;
}

Measured memory_bytes: 256
/* Dynamic Programming implementation of LCS problem */
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
void lcs(string X, string Y, int m, int n )
{
    int L[m+1][n+1];
    
    /* Following steps build L[m+1][n+1] in bottom up fashion. Note
     that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
    for (int i=0; i<=m; i++)
    {
        for (int j=0; j<=n; j++)
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i-1] == Y[j-1])
                L[i][j] = L[i-1][j-1] + 1;
            else
                L[i][j] = max(L[i-1][j], L[i][j-1]);
        }
    }
    
    // Following code is used to print LCS
    int index = L[m][n];
    
    // Create a character array to store the lcs string
    char lcs[index];
    
    // Start from the right-most-bottom-most corner and
    // one by one store characters in lcs[]
    int i = m, j = n;
    while (i > 0 && j > 0)
    {
        // If current character in X[] and Y are same, then
        // current character is part of LCS
        if (X[i-1] == Y[j-1])
        {
            lcs[index-1] = X[i-1]; // Put current character in result
            i--; j--; index--;     // reduce values of i, j and index
        }
        
        // If not same, then find the larger of two and
        // go in the direction of larger value
        else if (L[i-1][j] > L[i][j-1])
            i--;
        else
            j--;
    }
    
    // Print the lcs
    for (int i = 0; i < L[m][n]; i++) cout << lcs[i];
}

/* Driver program to test above function */
int main()
{
    string X, Y; cin >> X >> Y;
    lcs(X, Y, X.length(), Y.length());
    return 0;
}


Measured memory_bytes: 35456
# -*- coding: utf-8 -*-
# 整数の入力
n, m = map(int, input().split())
# スペース区切りの整数の入力
daystr = input().split()
homeworks = []
for s in daystr:
    homeworks.append(int(s))

days = sum(homeworks)
playable_days = n - days
if playable_days < 0:
    print(-1)
else:
    print(playable_days)

Measured memory_bytes: 10028
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,q;
  string s;
  cin >> n >> q >> s;
  vector<int> sum(n+1,0);
  bool last = false;
  for(int i=1;i<n+1;++i){
    if(last&&s[i-1]=='C'){
      last = false;
      sum[i] = sum[i-1]+1;
      continue;
    }
    if(s[i-1]=='A') last = true;
    else last = false;
    sum[i] = sum[i-1];
  }
  for(int i=0;i<q;++i){
    int l,r;
    cin >> l >> r;
    cout << sum[r]-sum[l] << endl;
  }
}

Measured memory_bytes: 1408
r ,c = map(int,input().split())
l = [[int(x) for x in input().split()] for i in [0]*r]
s = [0]*(c+1)
for j in range(r):
    l[j] += [sum(l[j])]
    for k in range(c+1):
        s[k] += l[j][k]
for m in range(r):
    print(*l[m])
print(*s)



Measured memory_bytes: 6248
a = int(input())
b = int(input())
c = int(input())
x = int(input())

res = 0
for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            s = i * 500 + j * 100 + k * 50
            if s == x:
                res += 1
print(res)

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>

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

using namespace std;
typedef long long int ll;
const int INF = 1000000000;
const double PI = 3.1415926535897932;
const ll MOD = 1000000007;

typedef pair<int, int> P;

int main()
{
    int h, w;
    char s[20][20];
    cin >> h >> w;
    rep(i, h) rep(j, w) cin >> s[i][j];

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

    int ans = 0;
    queue<P> que;
    rep(i, h) rep(j, w) {
        if (s[i][j] == '#') continue;
        rep(n, h) rep(m, w) d[n][m] = INF;
        que.push(P(i,j));
        d[i][j] = 0;
        while (que.size()) {
            P p = que.front();
            que.pop();
            rep(k, 4) {
                int x = p.first + dx[k];
                int y = p.second + dy[k];
                if (x >= 0 && x < h && y >= 0 && y < w && s[x][y] == '.' && d[x][y] == INF) {
                    que.push(P(x, y));
                    d[x][y] = d[p.first][p.second] + 1;
                }
            }
        }
        rep(n, h) rep(m, w) {
            if (d[n][m] != INF) ans = max(ans, d[n][m]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env ruby

h, w = gets.strip.split.map(&:to_i)
s = h.times.map { gets.strip.split('')}

def bomb_count(s, row, col, h, w)
  cnt = 0
  cnt += 1 if row - 1 >= 0 && s[row - 1][col] == '#'
  cnt += 1 if row + 1 < h  && s[row + 1][col] == '#'
  cnt += 1 if col - 1 >= 0 && s[row][col - 1] == '#'
  cnt += 1 if col + 1 < w  && s[row][col + 1] == '#'
  cnt += 1 if row - 1 >= 0 && col - 1 >= 0 && s[row - 1][col - 1] == '#'
  cnt += 1 if row + 1 < h  && col + 1 < w  && s[row + 1][col + 1] == '#'
  cnt += 1 if row - 1 >= 0 && col + 1 < w  && s[row - 1][col + 1] == '#'
  cnt += 1 if row + 1 < h  && col - 1 >= 0 && s[row + 1][col - 1] == '#'
  return cnt
end

s.each_with_index do |row_data, row|
  row_data.each_with_index do |col_data, col|
    print col_data == '#' ? '#' : bomb_count(s, row, col, h, w)
  end
  print("\n")
end

Measured memory_bytes: 3836
#include <bits/stdc++.h>
#define range(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, b) for (int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x) cerr << #x << " = " << (x) << endl;
#define int long long
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}
template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
	rep(i, v.size()) { os << v[i] << (i == v.size() - 1 ? "" : " "); }
	return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S>& p) {
	os << '(' << p.first << ',' << p.second << ')';
	return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
	for (T& x : v) { is >> x; }
	return is;
}

signed main() {
	int n, W;
	cin >> n >> W;
	
	vector<int> dp(100005, 1LL << 60);
	dp[0]= 0;
	rep(i,n){
		int w, v;
		cin >> w >> v;
		for (int j = 100000 - v; j >= 0; j--) {
			dp[j + v] = min(dp[j + v], dp[j] + w);
		}
	}

	int ans = 0;
	rep(i,dp.size()) if(dp[i] <= W) ans = i;
	cout << ans << endl;
}


Measured memory_bytes: 1024
N = int(input())
ans = [0] * N
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x - 1
            if n < N:
                ans[n] += 1
for i in ans:
    print(i)


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

int main() {
    int64_t n;
    cin >> n;
    vector<pair<int64_t, int64_t>> div;
    for(int64_t i = 2; i * i <= n; i++){
        if(n % i == 0){
            int64_t ex = 0;
            while(n % i == 0){
                ex++;
                n /= i;
            }
            div.emplace_back(i, ex);
        }
    }
    if(n != 1) div.emplace_back(n, 1);
    
    int64_t ans = 0;

    for(int64_t i = 0; i < div.size(); i++){
        int64_t cnt = 1;
        for(int64_t j = 0; j < div[i].second; j++){
            if(div[i].second >= cnt){
                div[i].second -= cnt;
                cnt++;
                ans++;
            }else{
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
#include <deque>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

#define INF 1e18
#define int long long

signed main() {
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    for(int i = sx; i < tx; i++) cout << "R";
    for(int i = sy; i < ty; i++) cout << "U";
    for(int i = sx; i < tx; i++) cout << "L";
    for(int i = sy; i < ty; i++) cout << "D";
    cout << "D";
    for(int i = sx; i < tx + 1; i++) cout << "R";
    for(int i = sy; i < ty + 1; i++) cout << "U";
    cout << "L";
    cout << "U";
    for(int i = sx; i < tx + 1; i++) cout << "L";
    for(int i = sy; i < ty + 1; i++) cout << "D";
    cout << "R" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MAX 100000
typedef long long ll;
typedef pair<ll,int> P;

int main(){
  ll N,A[110000],B[110000],ans=0;
  cin>>N;
  for(int i=0;i<=N;i++){
    cin>>A[i];
  }
  for(int i=0;i<N;i++) cin>>B[i];

  for(int i=0;i<N;i++){
    if(A[i]>B[i]) ans+=B[i];
    else{
      if(A[i]+A[i+1]>B[i]){
        ans+=B[i];
        A[i+1]-=(B[i]-A[i]);
      }else{
        ans+=A[i]+A[i+1];
        A[i+1]=0;
      }
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++) 
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
vector<string> str;
void f( string S )
{
	string tmp;
	bool flag = false;
	REP( i, (int)S.size() )
	{
		if( S[ i ] != ' ' && S[ i ] != ',' && S[ i ] != '.' )
		{
			flag = true;
			tmp += S[ i ];
			continue;
		}
		if( flag )
		{
			if( tmp.size() > 2 && tmp.size() < 7 )
			{
				str.emplace_back( tmp );
			}
			flag = false;
			tmp.clear();
		}
	}
}
int main()
{
	string S;
	getline( cin, S );

	f( S );

	REP( i, (int)str.size() )
	{
		i != str.size() - 1 ? cout << str[ i ] << " " : cout << str[ i ] << endl;
	}
	return 0;
}

Measured memory_bytes: 3100
N = int(input())
S = list(map(int, input().split(" ")))
Exchange_Number_of_times = 0
for i in range(N):
    minj = i
    for j in range(i, N):
        if S[j] < S[minj]:
            minj = j
    if i != minj:
        S[i], S[minj] = S[minj], S[i]
        Exchange_Number_of_times += 1
print(' '.join(map(str,S)))
print(Exchange_Number_of_times)



Measured memory_bytes: 5596
#include<bits//stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>h(n,0);
    for(int i=0;i<n;i++)
    cin>>h[i];

    vector<int>dp(n,0);
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    for(int i=2;i<n;i++)
    dp[i]=min(dp[i-1]+abs(h[i-1]-h[i]),dp[i-2]+abs(h[i-2]-h[i]));

    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1152
#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;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
int M, K;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin >> M >> K;
    if(K >= (1 << M)) {
        cout << -1 << endl;
        return 0;
    } else if(M == 0) {
        if(K == 0) cout << "0 0";
        else cout << -1;
        return 0;
    } else if(M == 1) {
        if(K == 1) cout << -1;
        else cout << "0 0 1 1" << endl;
        return 0;
    }
 
    for(int i = 0; i < (1 << M); i++) {
        if(i != K) cout << i << " ";
    }
    cout << K << " ";
    for(int i = (1 << M) - 1; i >= 0; i--)
        if(i != K) cout << i << " ";
    cout << K << " ";
 
}


Measured memory_bytes: 1792
#![allow(unused_imports)]
#![allow(non_snake_case)]
use proconio::{input, fastout};
use proconio::marker::{Chars, Bytes, Usize1};

#[fastout]
fn main() {
    input!{
        n:usize, d:i64,
        l: [(i64, i64); n]
    }
    let mut ans = 0;
    for &(x, y) in &l {
        if x * x + y * y <= d * d {
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 7820
IDENTIFICATION DIVISION.
PROGRAM-ID. 165D.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INP        PIC X(100).
01 A          PIC 9(07).
01 B          PIC 9(13).
01 N          PIC 9(13).
01 X          PIC 9(13).
01 FA         PIC 9(18).
01 FB         PIC 9(18).
01 OUT        PIC Z(17)9.
*>
PROCEDURE DIVISION.
  ACCEPT INP.
  UNSTRING INP DELIMITED BY ' '
      INTO A B N.
*>
  IF (N >= B)
    COMPUTE X = B - 1
  ELSE
    COMPUTE X = N
  END-IF.
*>
  COMPUTE FA = (A * X) / B
  COMPUTE FB = X / B
  COMPUTE FB = A * FB
  COMPUTE OUT = FA - FB. 
*>
  DISPLAY FUNCTION TRIM(OUT).
  STOP RUN.


Measured memory_bytes: 3912
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner stdIn = new Scanner(System.in);
        int N =stdIn.nextInt();
        String s="";
        if(N==0)s+=0;
        while(N!=0){
            if(N>0){
                if(N%2==1){
                    N--;
                    N=N/2;
                    N=-N;
                    s ="1"+s;
                }else{
                    N=N/2;
                    N=-N;
                    s ="0"+s;
                }
            }else{
                if(N%2==-1){
                    N--;
                    N=N/2;
                    N=-N;
                    s ="1"+s;
                }else{
                    N=N/2;
                    N=-N;
                    s ="0"+s;
                }
            }
        }
        System.out.println(s);
    }
}


Measured memory_bytes: 22868
#include <cstdio>
#include <memory.h>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <functional>
#include <iostream>
#include <set>
#include <list>
#include <map>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef unsigned long long llu;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
const ll MOD = 1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

priority_queue<pli, vector<pli>, greater<pli> > pq;
vector<pii> v[100000];

ll ldist[100000];
ll rdist[100000];

int ls[100000];
int rs[100000];

struct node {
	int u, v, c;
} edg[200000];

void dijk(int st, ll *dist, int *ss) {
	while (!pq.empty()) pq.pop();
	fill(dist, dist + 100000, (ll)1e18);
	
	ss[st] = 1; dist[st] = 0;
	pq.push({ 0, st });

	pli tv;
	pii tt;

	while (!pq.empty()) {
		tv = pq.top();
		pq.pop();

		if (tv.first != dist[tv.second]) continue;

		for (int i = 0; i < sz(v[tv.second]); i++) {
			tt = v[tv.second][i];

			if (dist[tt.second] > dist[tv.second] + tt.first) {
				dist[tt.second] = dist[tv.second] + tt.first;
				ss[tt.second] = 0;
				pq.push({ dist[tt.second], tt.second });
			}
			if (dist[tt.second] == dist[tv.second] + tt.first)
				ss[tt.second] = (ss[tt.second] + ss[tv.second]) % MOD;
		}
	}
}

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

	int s, t;
	scanf("%d %d", &s, &t);
	s--; t--;

	int a, b, c;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		a--; b--;
		v[a].push_back({ c, b });
		v[b].push_back({ c, a });

		edg[i] = { a, b, c };
	}

	dijk(s, ldist, ls);
	dijk(t, rdist, rs);
	ll ans = (ll)ls[t] * rs[s] % MOD;

	if (ldist[t] % 2 == 0) {
		for (int i = 0; i < n; i++)
			if (ldist[i] + rdist[i] == ldist[t] && ldist[i] == ldist[t] / 2) {
				ll tt = (ll)ls[i] * rs[i] % MOD;
				tt = tt * tt % MOD;
				ans = (ans - tt + MOD) % MOD;
			}
	}

	for (int i = 0; i < m; i++) {
		// printf("%d %d : ", edg[i].u + 1, edg[i].v + 1);
		if (ldist[edg[i].u] < (ldist[t] + 1) / 2 && ldist[edg[i].v] > ldist[t] / 2 && ldist[edg[i].u] + edg[i].c + rdist[edg[i].v] == ldist[t]) {
			// printf("pass");
			ll tt = (ll)ls[edg[i].u] * rs[edg[i].v] % MOD;
			tt = tt * tt % MOD;
			ans = (ans - tt + MOD) % MOD;
		}
		else if (ldist[edg[i].v] < (ldist[t] + 1) / 2 && ldist[edg[i].u] > ldist[t] / 2 && ldist[edg[i].v] + edg[i].c + rdist[edg[i].u] == ldist[t]) {
			// printf("pass");
			ll tt = (ll)ls[edg[i].v] * rs[edg[i].u] % MOD;
			tt = tt * tt % MOD;
			ans = (ans - tt + MOD) % MOD;
		}
		// printf("\n");
	}

	printf("%lld", ans);
}

Measured memory_bytes: 15220
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
ll a[200005],n,cnt,f[200005];
int main() 
{
	cin>>n;
	memset(f,0,sizeof(f));
	for(re int i=1;i<=n;i++)
		cin>>a[i];
	for(re int i=1;i<=n;i++){
		f[a[i]]=f[a[i]-1]+1;
	}
	ll maxx=0;
	for(re int i=1;i<=n;i++)
		maxx=max(maxx,f[i]);
	cout<<(n-maxx);
    return 0;
}

Measured memory_bytes: 3328
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cpp,赤波線出るけどコンパイルできる

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

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

    ll a,b,d,n,maxi=0,f=0,mini=INF,sum=0;
    ll w,h,x,y,k;
    //string str[3];
	cin>>n;
    vector<string> s(n);
    rep(i,n) cin>>s[i];
    map<char,ll> m[n];
    set<char> c;
    //rep(i,n) cin>>s[i];
    rep(i,n)rep(j,s[i].length()){
        m[i][s[i][j]]++;
        c.insert(s[i][j]);
    }
    //cout<<"a";

    map<char,ll> ans;
    for(auto itr=c.begin();itr!=c.end();++itr){
        ans[*itr] = INF;
    }
    for(auto itr=c.begin();itr!=c.end();++itr){
        rep(i,n) ans[*itr]=min(ans[*itr],m[i][*itr]);
    }
    vector<char> answer;
    for(auto itr=c.begin();itr!=c.end();++itr){
        rep(i,ans[*itr]) answer.push_back(*itr);
    }
    sort(all(answer));
    //answer.erase(answer.begin());
    rep(i,answer.size()) cout<<answer[i];
    ln; 

    return 0;
}



Measured memory_bytes: 3716
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>

int main() {
	ll n;
	cin >> n;
	vector<int>a(n);
	rep(i, n) {
		int k = i + 1;
		a[i] = k;
		if (k % 3 == 0 || k % 5 == 0) {
			a[i] = 0;
		}
	}
	ll sum(0);
	rep(i, n) {
		sum += a[i];
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 7012
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1000000007;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

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 main(){
    int N;
    cin >> N;
    vector<string> S(N);
    rep(i,N){
        cin >> S[i];
    }
    ll ans=0;
    rep(i,N){
        bool sym=true;
        rep(j,N){
            rep(k,N){
                if (S[j][k]!=S[k][j]){
                    sym=false;
                }
            }
        }
        if (sym){
            ans+=N-i;
        }
        rep(j,N){
            char s=S[j][0];
            rep(k,N){
                if (k!=N-1){
                    S[j][k]=S[j][k+1];
                }
                else {
                    S[j][k]=s;
                }
            }
        }
    }
    rep(i,N){
        bool sym=true;
        rep(j,N){
            rep(k,N){
                if (S[j][k]!=S[k][j]){
                    sym=false;
                }
            }
        }
        if (sym&&i!=0){
            ans+=N-i;
        }
        rep(j,N){
            char s=S[0][j];
            rep(k,N){
                if (k!=N-1){
                    S[k][j]=S[k+1][j];
                }
                else {
                    S[k][j]=s;
                }
            }
        }
    }
    cout << ans << endl;
}

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

bool eq(int i, string s, string t)
{
	int siz= s.size();
	for (int j = 0; j < siz; ++j)
		if(s[j] != t[(i+j)%siz])
			return false;
	return true;
}

int main()
{
	string s, t;
	cin >> s >> t;
	bool res = false;
	for (int i = 0; i < s.size(); ++i)
		if(eq(i, s, t))
			res = true;
	if(res)
		cout << "Yes\n";
	else
		cout << "No\n";
}

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

int main(){
  pair<long, long> s[50];
  pair<long, long> c[50];
  int N, M;
  cin >> N >> M;
  for(int i=0; i<N; i++){
    int a, b;
    cin >> a >> b;
    s[i] = make_pair(a,b);
  }
  for(int i=0; i<M; i++){
    int a, b;
    cin >> a >> b;
    c[i] = make_pair(a,b);
  }
  for(int i=0; i<N; i++){
    pair<int, long> p = make_pair(1,abs(c[0].first-s[i].first)+abs(c[0].second-s[i].second));
    for(int j=1; j<M; j++){
      long dist = abs(c[j].first-s[i].first)+abs(c[j].second-s[i].second);
      if(dist<p.second){
        p.first=j+1;
        p.second=dist;
      }
    }
    cout << p.first << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int a, b, c;
unordered_map<int, int> cnt;
int main() {
  cnt.clear();
  cin>>a>>b>>c;
  cnt[a]++;
  cnt[b]++;
  cnt[c]++;
  cout<<cnt.size()<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L


int Z_algo(string s) {
    int n = s.length();
    vector<int> z(n);
    int L = 0, R = 0;
    for (int i = 1; i < n; i++) {
        if (i > R) {
            L = R = i;
            while (R < n && s[R - L] == s[R]) R++;
            z[i] = R - L; R--;
        }
        else {
            int k = i - L;
            if (z[k] < R-i + 1) z[i] = z[k];
            else {
                L = i;
                while (R < n && s[R - L] == s[R]) R++;
                z[i] = R - L; R--;
            }
        }
    }
    int mx = 0;
    for (int i = 0; i < n; i++) mx = max(mx, min(i,z[i]));
    return mx;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n - 1);
    for (int i = 0; i < n - 1; i++) cin >> b[i];
    a[0] = b[0]; a[n - 1] = b[n - 2];
    for (int i = 1; i < n-1; i++) {
        a[i] = min(b[i - 1], b[i]);
    }

    long long sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];
    cout << sum;
    return 0;
}

Measured memory_bytes: 3540
// Copyright 2019 yaito3014
#include <bits/stdc++.h>
using namespace std;

int main(){
	long long A, B, K;
	cin >> A >> B >> K;
	if(A < K)B = max(0ll, B - (K - A));
	A = max(0ll, A - K);
	cout << A << " " << B << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N_FENWICK = 5e5,N=5e5+5;
int FENWICK[N_FENWICK+5];//cÎªÊ÷×´Êý×é 
inline int lowbit(int x){return x&(-x);}
void add(int x,int num){
	while(x<=N_FENWICK){
		FENWICK[x]+=num;
		x+=lowbit(x);//x+ lowbit(x)ÎªxµÄ¸¸Ç×½Úµã 
	}
}
int sum(int x){
	int ans=0;
	while(x){
		ans+=FENWICK[x];
		x-=lowbit(x);//c[i]´æ´¢i-lowbit[i]+1µ½iµÄÊý×éµÄÖµ£¬ËùÒÔÇóÇ°×ººÍÒª²»¶ÏÈ¥µô×îºóÒ»Î» 
	}
	return ans;
}
struct Q{
	int l,r,id;
	bool operator < (const Q &b)const {return r<b.r;}
}q[N];
int c[N],pre[N],ans[N];
int main(){
	int n,q1,L=0;scanf("%d%d",&n,&q1);
	for(int i=1;i<=n;i++)scanf("%d",c+i);
	for(int i=0;i<q1;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q,q+q1);
	for(int i=1;i<=n;i++){
		if(pre[c[i]])add(pre[c[i]],-1);
		add(pre[c[i]]=i,1);
		while(L<q1&&q[L].r==i)ans[q[L].id]=sum(i)-sum(q[L].l-1),L++;
	}
	for(int i=0;i<q1;i++)printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 17384
s=input()
i=1
s0=s[0]
ct=1
while i<len(s)-1:
  if s0==s[i]:
    s0=s[i:i+2]
    i+=2
  else:
    s0=s[i]
    i+=1
  ct+=1
if i>=len(s):
  print(ct)
elif s0==s[i]:
  print(ct)
else:
  print(ct+1)

Measured memory_bytes: 9248
//Name: Pankaj Mandrawal (pankaj_m05)
//Problem: OCD
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define mod 10000000009
#define sz(c) int((c).size())
#define sortall(x) sort(all(x))         
#define PI 3.1415926535897932384626     
#define all(c) (c).begin(), (c).end()
#define clr(x) memset(x, 0, sizeof(x))  
#define MAX32 numeric_limits< int >::max() 
#define MIN32 numeric_limits< int >::min()
#define rall(c) (c).rbegin(), (c).rend()
#define deb(x) cerr << #x << " = " << x << endl
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int) n; ++i)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, l, r) for(int i = (int)(l); i < (int)(r); ++i)
#define tr(c, it) for(typeof(c).begin() it = c.begin(); it != c.end(); it++)
#define deb2(x, y) cerr << #x << " = " << x << "," << #y << " = " << y << endl

using namespace std;

typedef long long ll;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< ll > vill;
typedef pair < int, int > pi;
typedef unsigned long long int ull;

ll mypow(ll x, ll y) { 
    if (y == 0) 
        return 1; 
    ll p = mypow(x, y / 2) % mod; 
    p = (p * p) % mod; 
    if (!(y & 1)) 
        return p;
    return (p * x) % mod; 
} 

void plssolve() {
	string s; cin >> s;
	for(int it = 0; it < sz(s); ++it)
		cout << 'x';
	cout << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(10);
    cout << fixed;
    int t = 1;
    //cin >> t;
    while(t--) {
        plssolve();
    }
    return 0;
}

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

int main()
{
  int h, w; cin >> h >> w;
  vector<vector<int>> c(10, vector<int>(10));
  rep(i, 10) rep(j, 10) cin >> c[i][j];
  vector<int> t(10);
  rep(i, h) rep(j, w) {
    int a; cin >> a;
    if (a >= 0) t[a]++;
  }

  rep(k, 10) rep(i, 10) rep(j, 10) {
      c[i][j] = min(c[i][j], c[i][k]+c[k][j]);
  }

  int ans = 0;
  rep(i, 10) {
    ans += t[i] * c[i][1];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e9;

int A[12345];

int KMPlast(string S){
  A[0] = -1;
  int j = -1;
  for (int i = 0; i < S.size(); i++) {
    while (j >= 0 && S[i] != S[j]) j = A[j];
    j++;
    A[i+1] = j;
  }
  return A[S.size()];
}


int f(string s,string t){
  string u=s+"#"+t;
  return KMPlast(u);
}

signed main(){
  int N;cin>>N;
  vector<string> s(N);
  for(int i=0;i<N;i++)cin>>s[i];
  typedef pair<int,int> P;
  typedef pair<int,P> IP;
  vector<IP> v;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      int a;
      if(i==j)a=f(s[i].substr(0,s[i].size()-1),s[j]);
      else a=f(s[i],s[j]);
      v.push_back(IP(a,P(i,j)));
    }
  }
  int sum=0,de=0;
  sort(v.rbegin(),v.rend());
  vector<bool> pused(N,0),bused(N,0);
  for(auto q:v){
    int a=q.first,p=q.second.first,b=q.second.second;
    if(pused[p]||bused[b])continue;
    de+=a;pused[p]=bused[b]=1;
  }
  for(int i=0;i<N;i++)sum+=s[i].size();
  cout<<sum-de<<endl;
}



Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
#define N 100055
#define ll long long
int dp[N][3],ar[N][3];
int main() {
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        for(int j=0; j<3; ++j)
            scanf("%d",&ar[i][j]);
    for(int i=1; i<=n; ++i) {
        dp[i][0] = max(dp[i-1][1] , dp[i-1][2]) + ar[i][0];
        dp[i][1] = max(dp[i-1][0] , dp[i-1][2]) + ar[i][1];
        dp[i][2] = max(dp[i-1][0] , dp[i-1][1]) + ar[i][2];
    }
    printf("%d",*max_element(dp[n] , dp[n]+3));
    return 0;
}


Measured memory_bytes: 2560
import sys

input = sys.stdin.readline

def main():
    a = 'a'
    b = 'b'
    c = 'c'
    y = 'Yes'
    n = 'No'
    ac = 0
    bc = 0
    N, A, B = map(int, input().split())
    s = input()
    for i in range(N):
        if s[i] == a:
            if ac < A + B:
                print(y)
                ac += 1
            else:
                print(n)
        elif s[i] == b:
            if ac < A + B and bc+1 <= B:
                print(y)
                ac += 1
                bc += 1
            else:
                print(n)
        else:
            print(n)

if __name__ == '__main__':
    main()

Measured memory_bytes: 4040
#include <iostream>
int main() {
    int m, f, r;
    for (std::cin >> m >> f >> r;
         m != -1 || f != -1 || r != -1;
         std::cin >> m >> f >> r) {
        int s = m + f;
        std::cout <<
            (
             (m == -1 || f == -1) ? 'F' :
             (s >= 80) ? 'A' :
             (s >= 65) ? 'B' :
             (s >= 50) ? 'C' :
             (s >= 30) ? ((r >= 50) ? 'C' : 'D') :
             'F'
            )
            << std::endl;
    }
}



Measured memory_bytes: 3080
n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = A[0]
if n%2 == 0:
    ans += sum(A[1:n//2])*2
else:
    ans += sum(A[1:n//2])*2 + A[n//2]

print(ans)

Measured memory_bytes: 31664
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
int n,k;
LL ans;
const int N=500010,mod=998244353;
LL jc[N],inv[N];
LL ksm(LL a,LL b,LL mod)
{
	LL res=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)res=res*a%mod;
	return res;
}
void YYCH()
{
	jc[0]=jc[1]=inv[0]=inv[1]=1;
	for(int i=1;i<=k;++i)jc[i]=jc[i-1]*i%mod;
	inv[k]=ksm(jc[k],mod-2,mod);
	for(int i=k-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%mod;
}
LL C(int n,int m){if(n<m)return 0;return jc[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{
	cin>>n>>k;YYCH();
	if(k<n)return puts("0")==233;
	for(int R=0,B;R<=k;++R)
	{
		B=k-R;
		if(R<B||R<n)continue;
		if(R==B)--B;
		(ans+=C(R+B,R)-C(R+B,2*R-n+1))%=mod;
	}
	cout<<(ans%mod+mod)%mod;
	return 0;
}

Measured memory_bytes: 8064