akhauriyash/Code-Regression huggingface dataset:
import sys

readline = sys.stdin.readline

N = int(readline())
S_list = [readline().rstrip() for i in range(N)]

count = 0
head_B = 0
tail_A = 0
AxB = 0
for s in S_list:
    for i in range(len(s)):
        if s[i:i+2] == 'AB':
            count += 1
    if s[0] == 'B':
        head_B += 1
    if s[-1] == 'A':
        tail_A += 1
    if (s[0] == 'B') != (s[-1] == 'A'):
        AxB += 1

if head_B == tail_A:
    if AxB > 0:
        print(count + head_B)
    else:
        print(count + max(head_B - 1, 0))
else:
    print(count + min(head_B, tail_A))



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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }
template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	os << v[0];
	for (int i = 1; i < v.size(); i++) os << " " << v[i];
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u; return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}


void Main() {
	int N, M; cin >> N >> M;
	vint A(N); cin >> A;
	sort(rbegin(A), rend(A));
	int sum = accumulate(begin(A), end(A), 0);
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (A[i] * 4 * M >= sum) cnt++;
	}
	if (cnt >= M) cout << "Yes" << endl;
	else cout << "No" << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

ll binomialCoeff(ll n, ll k) 
{ 
    ll C[k+1]; 
    memset(C, 0, sizeof(C)); 
  
    C[0] = 1;  // nC0 is 1 
  
    for (ll i = 1; i <= n; i++) 
    { 
        // Compute next row of pascal triangle using 
        // the previous row 
        for (ll j = min(i, k); j > 0; j--) 
            C[j] = C[j] + C[j-1]; 
    } 
    return C[k]; 
} 

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int x=nxt(),a=nxt(),b=nxt();
    if(abs(x-a)<=abs(x-b))
        cout<<"A\n";
    else
        cout<<"B\n";
    
    
    return 0;   
}




 
 


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int N;
long long a[100001];
long long cnt, x;

void solve() {
    for(int i = 1; i < N; i++) {
        long long sum = a[i] + a[i-1];
        long long tmp = max(sum - x, 0LL); 
        cnt += tmp;
        a[i] = max(0LL, a[i] - tmp);
    }
    cout << cnt << endl;
}

int main() {
    cin >> N >> x;
    for(int i = 0; i < N; i++) cin >> a[i];
    solve();
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long int LL;
typedef pair <LL, int> pii;
const LL MOD = 1000000007LL;
const int MAXN = 100005, MAXM = 200005;

int n, m, s, t, g[MAXN], nxt[MAXM << 1], to[MAXM << 1];
int val[MAXM << 1], edgeSize;
LL dp1[MAXN], dp2[MAXN], ans, d1[MAXN], d2[MAXN];

void addEdge(int u, int v, int w){
	nxt[++ edgeSize] = g[u];
	to[g[u] = edgeSize] = v;
	val[edgeSize] = w;
}
void dijkstra(int st, LL d[], LL dp[]){
	priority_queue <pii, vector <pii>, greater <pii> > q;
	int i, p; pii now;
	for(i = 1; i <= n; ++ i)
		d[i] = 0x3f3f3f3f3f3f3f3fLL, dp[i] = 0;
	d[st] = 0, dp[st] = 1;
	q.push(pii(0, st));
	while(!q.empty()){
		now = q.top(); q.pop();
		if(now.fi != d[now.se])
			continue;
		for(p = g[now.se]; p; p = nxt[p])
			if(d[to[p]] > now.fi + val[p]){
				q.push(pii(d[to[p]] = now.fi + val[p], to[p]));
				dp[to[p]] = dp[now.se];
			}else if(d[to[p]] == now.fi + val[p])
				dp[to[p]] = (dp[to[p]] + dp[now.se]) % MOD;
	}
}
int main(){
	int i, u, v, w, j;
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for(i = 1; i <= m; ++ i){
		scanf("%d%d%d", &u, &v, &w);
		addEdge(u, v, w), addEdge(v, u, w);
	} dijkstra(s, d1, dp1);
	dijkstra(t, d2, dp2);
	ans = dp1[t] * dp1[t] % MOD;
	for(i = 1; i <= n; ++ i){
		if(d1[i] * 2 == d1[t] && d1[i] + d2[i] == d1[t])
			ans = (((ans - (dp1[i] * dp2[i] % MOD) * (dp1[i] * dp2[i] % MOD)) % MOD) + MOD) % MOD;
		if(d1[i] * 2 >= d1[t]) continue;
		for(j = g[i]; j; j = nxt[j]){
			if(d1[i] + val[j] != d1[to[j]] || d1[to[j]] + d2[to[j]] != d1[t])
				continue;
			if(d1[to[j]] * 2 > d1[t])
				ans = (((ans - (dp1[i] * dp2[to[j]] % MOD) * (dp1[i] * dp2[to[j]] % MOD)) % MOD) + MOD) % MOD;
		}
	} printf("%d\n", int(ans));
	return 0;
}

Measured memory_bytes: 12116
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n,k,x[100010],mi = INF;
	cin >> n >> k;
	for(int i = 0;i < n;i++) cin >> x[i];
	for(int i = 0;i < n - k + 1;i++){
		int a = x[i],b = x[i + k - 1];
		if(a * b >= 0) chmin(mi,max(abs(a),abs(b)));
		else chmin(mi,min(-a,b) * 2 + max(-a,b));
	}
	cout << mi << endl;
	return 0;
}

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

int main()
{
     int h,w;
  cin >> h >> w;
  while(h!=0 && w!=0){
    int i,j;
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	  if(i==0 || j==0) cout<<"#";
	  else
	  if(i==h-1 || j==w-1) cout<<"#";
	  else cout<<".";

      }
      cout << endl;
    }
    cout << endl;
    cin >> h >> w;
  }
    return 0;
}



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

int main(){
    int N,K; cin>>N>>K;
    vector<int> h(N);
    rep(i,N) cin>>h[i];
    vector<int> dp(N,2147483647);
    
    dp[0]=0;
    for(int i=0; i<N-1; i++){
        for(int j=1; j<=K; j++){
            if(i+j >=N) break;
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j]-h[i]));
        }
    }

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


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

#define NREP() for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
using ll = long long;
const static ll MOD = 1e9 + 7;

ll solve(ll n) {
    ll divider = 5;
    ll ans = 0;
    while (divider <= n) {
        ans += (n / 2) / divider;
        divider *= 5;
    }
    return ans;
}

int main(int argc, char *argv[]) {
    ll n;
    cin >> n;

    if (n % 2 != 0) {
        cout << 0 << endl;
    } else {
        cout << solve(n) << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define F(i,j,k,in) for(ll i=j;i<k;i+=in)
#define DF(i,j,k,in) for(int i=j;i>=k;i-=in)
#define feach(it,l) for (auto it = l.begin(); it != l.end(); ++it)
#define fitr(it,it1,itr2) for(auto it=itr1;it!=itr2;++it)
#define fall(a) a.begin(),a.end()
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define eq equal_range
#define fs first
#define ss second
#define ins insert
#define mkp make_pair
#define PI 3.1415926535897932384626433832795
#define endl "\n"
using namespace std;
typedef vector<ll> vll;
typedef vector<int> vin;
typedef vector<char> vch;
typedef vector<string> vst;
typedef vector<vector<ll>> vvll;
typedef vector<pair<ll,ll>> vpll;
typedef set<ll> sll;
typedef set<int> sint;
typedef set<char> sch;
typedef set<string> sst;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef map<ll,ll> mll;
typedef pair<ll,ll> pll;
const ll MOD=1000000007;
ll pwr(ll b,ll p){ll res=1;while(p){if(p&1) {res*=b; p--;}else{b*=b; p>>=1;}}return res;}
const int maxn = 2e5;
int T[maxn];

int main()
{
  ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL);
   int n ,k;
   cin>>n>>k;
   ll tot=0;
   F (i,0,n,1) cin>>T[i];
   F (i,1,n,1) {
     if (T[i]-T[i-1]<k) tot+=(T[i]-T[i-1]);
     else tot+=k;
   }
   tot+=k;
  cout<<tot;

return 0;
}




Measured memory_bytes: 4376
#include <stdio.h>
int main(void){
   int m,f,r;
   
   while(1){
    scanf("%d %d %d", &m, &f, &r);

    if(m == -1 && f == -1 && r == -1) 
        break;
    else if(m == -1 || f == -1)
        printf("F\n");
    else if((m+f)>=80)
        printf("A\n");
    else if((m+f)>=65 && (m+f)<80)
        printf("B\n");
    else if((m+f)>=50 && (m+f)<65)
        printf("C\n");
    else if((m+f)>=30 && (m+f)<50 && r<50)
       printf("D\n");
    else if((m+f)>=30 && (m+f)<50 && r>=50)
        printf("C\n");
    else if((m+f)<30)
        printf("F\n");
        
   }
   return 0;
   
    

    

    
}



Measured memory_bytes: 2104
#include <iostream>
using namespace std;
#define MAX 15
#define INF 10000


int main()
{
    int v, e, s, t, p;
    int d[MAX][MAX];
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            d[i][j] = INF;
        }
    }
    for (int i = 0; i < MAX; i++) {
        d[i][i] = 0;
    }
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        cin >> s >> t >> p;
        d[s][t] = p;
    }
    
    int dp[1<<MAX][MAX];
    for (s = 0; s < 1 << v; s++) {
        fill(dp[s], dp[s] + v, INF);
    }
    dp[(1 << v) - 1][0] = 0;
    for (int s = (1 << v) - 2; s >= 0; s--) {
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                if (!(s >> j & 1)) {
                    dp[s][i] = min(dp[s][i], dp[s | 1 << j][j] + d[i][j]);
                }
            }
        }
    }
    if (dp[0][0] == INF) {
        cout << -1 << endl;
    }else{
        cout << dp[0][0] << endl;
    }
    
    

    return 0;
}

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

using namespace std ;

int n, m ; 

const int MAXN = 310 ; 

int top[MAXN] ; 
int a[MAXN][MAXN] ; 

bool de[MAXN] ; 

int cnt[MAXN] ; 

bool check(int x) { 

		memset(cnt, 0, sizeof cnt) ; 
		for (int i = 1; i <= n; i ++) { 
				top[i] = 1; 
				cnt[a[i][1]] ++ ;
		}

		memset(de, 0, sizeof de) ; 

		while (1) { 
				bool flag = 0 ; 
				for (int i = 1; i <= m; i ++) { 
						if (cnt[i] > x) { 
								de[i] = 1;  
								for (int i = 1; i <= n; i ++) { 
										while (de[a[i][top[i]]]) {
												cnt[a[i][top[i]]] -- ; 
												top[i] ++ ; 
												cnt[a[i][top[i]]] ++ ; 
										}
								}
								flag = 1;  
								break ; 
						}
				}
				if (!flag) break ; 
		}
		for (int i = 1; i <= m; i ++) if (!de[i]) return 1 ; 
		return 0 ;
}


int main() { 

		scanf("%d%d", &n, &m) ; 

		for (int i = 1; i <= n; i ++) { 
				for (int j = 1; j <= m; j ++) scanf("%d", &a[i][j]) ; 
		}

		int l = 1, r = n ; 
		while (l < r) { 
				int mid = (l + r) >> 1; 
				if (check(mid)) r = mid;
				else l = mid + 1; 
		}
		printf("%d\n", l) ; 
}



Measured memory_bytes: 640
#include<iostream>
#include<math.h>
using namespace std;
int main(){
	int a,b,c,x,y;
	int  s,s1,s2;
	cin>>a>>b>>c>>x>>y;
	s=a*x+b*y;
	if(a+b>=2*c){
		if(x>=y)
		s=2*c*min(x,y)+a*(x-y);
		else
		s=2*c*min(x,y)+b*(y-x);
		s1=2*c*max(x,y);		
	}
	s1=2*c*max(x,y);
	s=min(s1,s);
	cout<<s<<endl;
	} 

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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll n,m;
ll a[3][2010];
double tab[2010][2010],p[2010];
double E[3][2010];
double score[]={5.0,3.0,2.0};

double win(ll j,ll ap){
  if(ap>m) return 1.0;
  else if(ap>0) return p[ap-1];
  else return 0.0;
}

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

  cin>>n>>m;
  rep(i,n)rep(j,3)cin>>a[j][i];

  rep(i,m+1)tab[i][0]=pow(2.0/3.0,i);
  rep(i,m+1)tab[i][i]=pow(1.0/3.0,i);

  repl(i,1,m+1)repl(j,1,i){
    tab[i][j]=(tab[i-1][j-1]*(1.0/3.0)+tab[i-1][j]*(2.0/3.0));
  }

  p[0]=tab[m][0];
  repl(i,1,m+1){
    p[i]=p[i-1]+tab[m][i];
  }

  rep(k,3){
    rep(i,m+1){
      ll crtpoint=a[k][0]*i;
      double sum=0;

      vector<double> pfx(n+1,1.0),sfx(n+1,1.0),pfx2(n+1,0.0);
      double cp=1.0;
      repl(j,1,n){
        ll r=(crtpoint+a[k][j]-1)/a[k][j];
        cp*=win(j,r);
        pfx[j]=cp;
      }
      cp=1.0;
      for(ll j=n-1;j>=1;j--){
        ll r=(crtpoint+a[k][j]-1)/a[k][j];
        cp*=win(j,r);
        sfx[j]=cp;
      }

      // 1
      sum+=pfx[n-1];

      // 2
      repl(j,1,n){
        ll r=(crtpoint+a[k][j]-1)/a[k][j];
        sum+=(1.0-win(j,r))*pfx[j-1]*sfx[j+1];
        pfx2[j]=win(j,r)*pfx2[j-1];
        pfx2[j]+=(1.0-win(j,r))*pfx[j-1];
      }

      // 3
      repl(j,1,n){
        ll r=(crtpoint+a[k][j]-1)/a[k][j];
        sum+=(1.0-win(j,r))*pfx2[j-1]*sfx[j+1];
      }

      E[k][i]+=sum*score[k];

      // worst
      cp=1.0;
      repl(j,1,n){
        ll r=(crtpoint+a[k][j]-1)/a[k][j];
        cp*=(1.0-win(j,r));
      }
      E[k][i]+=cp*(-1.0);
    }
  }

  double res=-1e18;
  rep(i,m+1)rep(j,m+1){
    ll k=m-i-j;
    if(k<0)continue;
    maxch(res,E[0][i]+E[1][j]+E[2][k]);
  }

  printf("%.10f\n", res);

  return 0;
}



Measured memory_bytes: 26232
N = int(input())
p = list(map(int,input().split()))
ans = 0
i=0
while i<N:
    if p[i]==i+1:
        #p[i],p[i+1] = p[i+1],p[i]
        ans += 1
        i += 2
    else:
        i+=1

print(ans)

Measured memory_bytes: 52908
/*input
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
*/
 
#include <unordered_map>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <climits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stdint.h>
 
using namespace std;
 
/*******  All Required define Pre-Processors and typedef Constants *******/
#define ar array
#define scd(t) scanf("%d",&t)
#define scld(t) scanf("%ld",&t)
#define sclld(t) scanf("%lld",&t)
#define scc(t) scanf("%c",&t)
#define scs(t) scanf("%s",t)
#define scf(t) scanf("%f",&t)
#define sclf(t) scanf("%lf",&t)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define tests int r; cin >> r; while(r--)
#define MP make_pair
#define PI acos(-1)
typedef pair<long long, long long> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
#define godspeed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
 
#define M(x) ((x)%(1000000007))
 
 int64 fact(int n) {
   int64 count = 1;
   for(int64 i = 1;i<=n;i++){
   		count = M(count * i);
   }
   return count;
}
 
 
 
int main() {
	godspeed;
	int n;
	cin>>n;
	int arr[3][n];
	int dp[3][n];
	rep(i,n){
		int x;
		int y; 
		int z;
		cin>>x>>y>>z;
		arr[0][i] = x;
		arr[1][i] = y;
		arr[2][i] = z;
		if(i==0){
			dp[0][0] = x;
			dp[1][0] = y;
			dp[2][0] = z;
		}
	}
	for(int i = 1;i<n;i++){
		rep(j,3){
			dp[j][i] = arr[j][i] + max(dp[(j+1)%3][i-1], dp[(j+2)%3][i-1]);
		}
	}
	int ans = max(dp[0][n-1],max(dp[1][n-1],dp[2][n-1]));
	cout<<ans<<endl;
}

Measured memory_bytes: 5920
#!/usr/bin/env python3
import sys


def solve(N: int, K: int):
    answer = 1
    while True:
        if K**(answer-1) <= N < K**answer:
            break
        answer += 1
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include<stdio.h>
int main(void)
{
    int h,r;
	scanf("%d",&h);
	scanf("%d",&r);
	if(h + r ==0){
	       printf("%d\n",0);
	}
	else if(h + r<0){
	          printf("%d\n",-1);
	}
	else if(h + r>0){
		      printf("%d\n",1);
	}
	return 0;
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<ll> VI; typedef pair<ll,ll> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amin(T& a,T b){ a=min(a,b);}
template <class T> void amax(T& a,T b){ a=max(a,b);}


int main()
{
	//cin.tie(0); ios_base::sync_with_stdio(false);
	
	int n; cin >>n;
	VI a(n), b(n);
	rep(i,n) cin >>a[i];
	rep(i,n) cin >>b[i];
	
	bool ok=true;
	rep(i,n) if(a[i] <b[i]) ok=false;
	if(ok){ puts("0"); return 0;}
	
	ll sma = accumulate(all(a),0LL);
	ll smb = accumulate(all(b),0LL);
	if(smb > sma){puts("-1"); return 0;}
	
	vector<pii> vp(n);
	rep(i,n) vp[i] = pii(a[i], b[i]);
	VI odf(n);
	rep(i,n) odf[i] = vp[i].first - vp[i].second;
	sort(all(odf)); reverse(all(odf));
	int ans =0;
	auto svodf = odf;
	int r=n-1;
	rep(l,n){
			ll z = odf[l];
			for(;r>=l;){
				if(odf[r] <0){
					if(odf[r] + z >= 0){
						z +=odf[r]; odf[r]=0; r--;
					}else{
						odf[r] +=z; z=0; break;
					}
					//dbg(l,r,z,odf[r]);
				}else{break;}
			}
			//dbg("00",l,odf[l],z);
			if(z !=odf[l]) odf[l]=0;
	}
	//for(auto x :odf) printf("%d, ",x); puts("");
	rep(i,n) if(odf[i] != svodf[i]) ans++;
	cout <<ans <<"\n";
	return 0;
}


Measured memory_bytes: 4864
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
typedef long long ll;
const ll INF = 1LL<<60;

int main(){
    int N; cin >> N;
    vector<ll> A(N), B(N), C(N);
    REP(i,N) cin >> A[i] >> B[i];
    REP(i,N) C[i] = min(A[i], B[i]);
    int idx = -1;
    ll m = INF;
    ll s = 0;
    REP(i,N) {
        s += A[i];
        if (A[i]>C[i] && m>B[i]) {
            m = B[i];
            idx = i;
        }
    }
    if(m==INF) {
        cout << 0 << endl;
    }
    else {
        cout << s - C[idx] << endl;
    }
    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int a[3][3];
   f(i,0,3){
      f(j,0,3){
         cin >> a[i][j];
      }
   }
   int n;
   cin >> n;
   map<int,int> cnt;
   f(i,0,n){
      int x;
      cin >> x;
      cnt[x] = 1;
   }
   // Row;
   f(i,0,3){
      int s = 0;
      int r = 0;
      f(j,0,3){
         s += cnt[a[i][j]];
         r += cnt[a[j][i]];
      }
      if(s == 3 or r == 3){
         cout << "Yes\n";
         return 0;
      }
   }
   if(cnt[a[0][0]] + cnt[a[1][1]] + cnt[a[2][2]] == 3 or cnt[a[0][2]] + cnt[a[1][1]] + cnt[a[2][0]] == 3){
      cout << "Yes";
   }else{
      cout << "No\n";
   }
   return 0;
} 

Measured memory_bytes: 256
def main():
    H, W = map(int, input().split())
    board = [list(input()) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if board[i][j] == ".":
                count = 0
                for k in range(-1, 2):
                    for l in range(-1, 2):
                        if 0 <= i + k < H and 0 <= j + l < W:
                            if board[i + k][j + l] == "#":
                                count += 1
                board[i][j] = str(count)
    for i in range(H):
        print("".join(map(str, board[i])))
main()

Measured memory_bytes: 3188
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
bool compare(int a,int b)
{
return a>b;
}
int main(){
	long double  a,b,c,e,f,g;
	cin>>a>>b>>c;
	int n=0;
	while(1){
		n++;
		e=a;g=b;f=c;
		if((int)a%2!=0||(int)b%2!=0||(int)c%2!=0){
			cout<<--n<<endl;
			break;
		}
		if((int)a%2==0&&(int)b%2==0&&(int)c%2==0&&(a==b&&b==c)){
			cout<<-1<<endl;
			break;
		}
		a=(g+f)/2.0;
		b=(e+f)/2.0;
		c=(e+g)/2.0;
		if(a>(int)a||b>(int)b||c>(int)c){
			n--;
			cout<<n<<endl;
			break;
		}
			
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
const int mod = 1000000007;
const int max_n = 200005;
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;
}
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}comb(max_n);
int main(){
    CST(9);
    double r;cin >>r;
    cout << r*3.1415926535*2 <<endl;
}

Measured memory_bytes: 6236
package main

import (
	"fmt"
)

func main() {
	var a, b, c, d int
	fmt.Scan(&a, &b, &c, &d)

	if a+b > c+d {
		fmt.Println("Left")
	} else if a+b < c+d {
		fmt.Println("Right")
	} else {
		fmt.Println("Balanced")
	}
}


Measured memory_bytes: 512
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;


public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    ArrayList<long[]> al = new ArrayList();
    int n = sc.nextInt();
    for(int i = 0; i < n; i++) {
      long x = sc.nextLong();
      long l = sc.nextLong();
      long[] tmp = {x-l,x+l};
      al.add(tmp);
    }
    Collections.sort(al, new Comparator<long[]>() {
      public int compare(long[] a1, long[] a2) {
        return Long.compare(a1[1],a2[1]);
      }
    });
    int ans = 1;
    long r1 = al.get(0)[1];
    for(int i = 1; i < n; i++) {
      long l1 = al.get(i)[0];
      long r2 = al.get(i)[1];
      if(l1>=r1) {
        ans++;
        r1=r2;
      }
    }
    System.out.println(ans);
  }

}


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

int main(){
    double a,b,v,w,t;
    cin >> a >> v;
    cin >> b >> w;
    cin >> t;
    if(b > a){
        if(b+t*w <= a + t*v){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }else{
        if(b-t*w >= a - t*v){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
}

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

namespace _0241
{
    class Program
    {
        static void Main(string[] args)
        {
            string[,] operations = new string[,]
            {
                 {"+0" ,"+1" ,"+2" ,"+3"}
                ,{"+1" ,"-0" ,"+3" ,"-2"}
                ,{"+2" ,"-3" ,"-0" ,"+1"}
                ,{"+3" ,"+2" ,"-1" ,"-0"}
            };

            while (true)
            {
                int n = RInt();
                if (n == 0) break;

                for (int k = 0; k < n; k++)
                {

                    int[] vs = RArInt();
                    int[] ar1 = vs.Take(4).ToArray();
                    int[] ar2 = vs.Skip(4).Take(4).ToArray();

                    int[] res = new int[ar1.Length];
                    for (int i = 0; i < ar1.Length; i++)
                    {
                        for (int j = 0; j < ar2.Length; j++)
                        {
                            string operation = operations[i, j];
                            if(operation[0] == '+')
                            {
                                res[int.Parse(operation[1].ToString())] += ar1[i] * ar2[j];
                            }
                            else
                            {
                                res[int.Parse(operation[1].ToString())] -= ar1[i] * ar2[j];
                            }
                        }
                    }
                    Console.WriteLine(WAr(res));
                }
            }
        }
        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RArSt(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RArInt(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RArLong(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RArDouble(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }
}



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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 32768);
    static PrintWriter out = new PrintWriter(System.out);
    static StringTokenizer t;

    static String sn() {
        while (t == null || !t.hasMoreTokens()) {
            try {
                t = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                throw new RuntimeException();
            }
        }
        return t.nextToken();
    }

    static int ni() {
        return Integer.parseInt(sn());
    }

    static long nlo() {
        return Long.parseLong(sn());
    }

    public static void main(String args[]) {
        int t = 1;//ni();
        while (t-- > 0) {
            solve();
        }
        out.close();
    }

    static long mod = 998244353;

    static long pro(long a, long b) {
        return (a % mod * b % mod) % mod;
    }

    static long add(long a, long b) {
        return (a + b) % mod;
    }

    static int maxn = 200005;

    static long func(long b, long n) {
        if (b > n)
            return n;
        return (n % b + func(b, n / b));
    }

    static void solve() {
        int n = ni();
        int a = ni();
        int x[] = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            x[i] = ni();
            sum += x[i];
        }
        long dp[][][] = new long[52][52][2502];
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                for (int k = 0; k <= sum; k++) {
                    if (j - 1 >= 0 && x[i - 1] <= k)
                        dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i - 1]];
                    else
                        dp[i][j][k] = dp[i - 1][j][k];
                }
            }
        }
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += dp[n][i][a * i];
        }
        out.println(ans);
    }
}

Measured memory_bytes: 89120
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <fstream>
 
using namespace std;
 
#define INF 1000000000
#define EPS 1e-9
#define PI acos(-1)
 
typedef long long ll;

#define MAX_T 51
#define MAX_P 11
#define MAX_R 501


int main(){

  while(true){

    int T, P, R;
    int pID[MAX_T][MAX_P];
    int sum_time[MAX_T];
    int correct_count[MAX_T];
    bool used[MAX_T];

    memset(pID, 0, sizeof(pID));
    memset(sum_time, 0, sizeof(sum_time));
    memset(correct_count, 0, sizeof(correct_count));
    memset(used, 0, sizeof(used));

    cin >> T >> P >> R;
    if(T == 0)
      break;

    while(R > 0){
      R--;

      int id,p,t;
      string str;
      cin >> id >> p >> t >> str;

      if(str == "CORRECT"){
	correct_count[id]++;
	sum_time[id] += t + pID[id][p]*1200;
      }
      else{
	pID[id][p]++;
      }

    }

    int ret = 0;

    while(ret < T){
      ret++;
      int id,count,time;
      count = -1;
      time = INF;
      for(int i = 1; i <= T; i++){
	if(!used[i] && count < correct_count[i]){
	  id = i;
	  count = correct_count[i];
	  time = sum_time[i];
	}
	else if(!used[i] && count == correct_count[i] && time > sum_time[i]){
	  id = i;
	  time = sum_time[i];
	}
      }

      used[id] = true;
      cout << id << " " << count << " " << time << endl;

    }

  }

  return 0;

}

Measured memory_bytes: 1216
#include <iostream>

using namespace std;

int Array_digit[5];//桁を各個保管する

int division_digit(int num){
    string digit_chalacter=to_string(num);
    int digit_num=digit_chalacter.length();
    for(int i=0;i<digit_num;i++){
        string a;
        a+=digit_chalacter[i];
        Array_digit[i]=stoi(a);
    }
    return digit_num;//returnは桁数とする
}

int main(){
    int N,A,B,num,ans=0;
    cin>>N>>A>>B;
    for(int i=1;i<=N;i++){
        int a=0;
        num=division_digit(i);
        for(int j=0;j<num;j++){
            a+=Array_digit[j];
        }
        if(A<=a&&a<=B){
            ans+=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;
typedef long long ll;
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 rep(i,j,n) for (ll i = j; i < (n); i++)
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL << 60;
// ll dp[100010];

int main(){

  int n,m;cin>>n>>m;
  vector<bool>ok(n+1,true);
  rep(i,0,m){
    int a;cin>>a;
    ok[a]=false;
  }

  vector<ll>dp(n+1,0);
  dp[0]=1;
  rep(i,0,n){
    for(int next=i+1;next<=min(i+2,(ll)n);next++){
      if(ok[next]){
        dp[next]+=dp[i];
        dp[next]%=mod;
      }
    }
  }

  out(dp[n]);

  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <iostream>
using namespace std;


long long int h[100010], dp[100100];

int N, L;

long long int q(int k) {
    int i;
    if (dp[k] != -1) return dp[k];

    if (k == 0 || k == 1) dp[k] = 0;
    else if (k == 2) dp[k] = abs(h[N-k] - h[N-k+1]);
    else {
        long long int temp, min = 9999999999;
        for (i = 1; (i <= L && k-i > 0); i++) {
            temp = q(k-i) + fabs(h[N-k] - h[N-k+i]);
            if (min > temp) min = temp;
        }
        dp[k] = min;
    }

    return dp[k];
}

int main() {
    int k;

    cin >> N >> L;

    for (k = 0; k < N; k++) {
        cin >> h[k];
    }

    for (k = 0; k < 100100; k++) {
        dp[k] = -1;
    }

    cout << q(N) << endl;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);

/* -----  2019/05/25  Problem: ABC 127 D / Link: http://abc127.contest.atcoder.jp/tasks/abc127_d  ----- */


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

	LL N, M; cin >> N >> M;
	vector<LL> a(N);
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
	}
	vector<PLL>c;
	FOR(i, 0, M) {
		LL x, y; cin >> x >> y;
		c.push_back(PLL(y, x));
	}
	RSORT(c);
	SORT(a);
	DD(De(a));
	LL k = 0;
	FOR(i, 0, M) {
		DD(de(c[i]));
		LL idx = lower_bound(a.begin() + k, a.end(), c[i].first) - a.begin();
		DD(de(idx));
		idx = min(idx, k + c[i].second);
		idx = min(idx, N);
		FOR(p, k, idx) {
			a[p] = c[i].first;
		}
		DD(De(a));
		k = idx;
	}
	LL ans = accumulate(ALL(a), 0LL);

	cout << (ans) << "\n";

	return 0;
}


Measured memory_bytes: 3188
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String a = sc.next();
    String b = sc.next();
    if(a.equals(b)){
      System.out.println("H");
    }else{
      System.out.println("D");
    }
  }
}


Measured memory_bytes: 22996
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); }
void log()(){ writeln(""); } void log(T, A ...)(T t, lazy A a){ if(DEBUG) write(t, " "), log(a); } bool DEBUG = 0; 
string rstring(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T rtype(T)(){ return rstring.to!T; } alias rint = rtype!int, rlong = rtype!long, rreal = rtype!real;
T[] rtypes(T)(int n){ return n.iota.map!(i => rtype!T()).array; } alias rint = rtypes!int, rlong = rtypes!long, rreal = rtypes!real;
T[][] rtypess(T)(int n, int m){ return n.iota.map!(i => rtypes!T(m)).array; } alias rint = rtypess!int, rlong = rtypess!long, rreal = rtypess!real;

// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //

void solve(){
	int n = rint;
	
	foreach(i; 1 .. 10) foreach(j; 1 .. 10){
		if(i * j == n){
			"Yes".writeln;
			return;
		}
	}
	
	"No".writeln;
}


Measured memory_bytes: 256
n, r = gets.split.map &:to_i
res = (1..r).map{ gets.split.map(&:to_i) }.sort_by(&:last) + [[n+1, n+1]]
hash ={nil => 0}
until res.empty?
	poster, prior = res.shift
	new_hash = Hash.new(Float::INFINITY)
	
	hash.each{|min, cost|
		min = poster if !min || poster < min 
		new_hash[min] = cost if cost < new_hash[min]
		c = cost + (prior - min) * 2
		new_hash[nil] = c if c < new_hash[nil]
	}
	hash = new_hash
end
p hash[nil] + n + 1

Measured memory_bytes: 17016
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF (1<<30)-1
using ll = long long;
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

inline map<ll,int> sieve(ll n){
  map<ll,int> PrimeNumber;
  for(ll i = 2; i*i <= n; i++){
    while(n % i == 0){
      PrimeNumber[i]++;
      n /= i;
    }
  }
  if(n != 1) PrimeNumber[n] = 1;
  return PrimeNumber;
}

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  ll n; cin >> n;
  const int MOD = 1e9+7;
  map<int,int> mp;
  rep(i,n){
    auto res = sieve(i+1);
    for(auto x : res) mp[x.first] += x.second;
  }
  ll ans = 1;
  for(auto x : mp){
    ans *= x.second+1;
    ans %= MOD;
  }
  cout << ans;
  cout << "\n";
  return 0;
}


Measured memory_bytes: 3632
n = int(input())
a = list(map(int, input().split()))

l = [0]*(10**6 +1)
for i in a:
    l[i]+=1
num = 0

for i in range(10**6+1):
    if l[i] == 1:
        num += 1
    if l[i] != 0:
        for j in range(2*i, 10**6+1, i):
            if l[j]:
                l[j] += 1
print(num)

Measured memory_bytes: 32180
n = int(input())
s1 = input()
s2 = input()
mod = 10**9+7
dp = [-1] * (n)
if s1[0] == s2[0]:
    dp[0] = 1 
else:
    dp[0] = 2
for i in range(n-1):
    if dp[i] == -1:
        continue
    if s1[i] == s2[i]:
        dp[i+1] = (dp[i] * 2) % mod
        continue
    if i+2 >= n:
        break
    if s1[i+2] == s2[i+2]:
        dp[i+2] = dp[i]
    else:
        dp[i+2] = (dp[i] * 3) % mod

ans = dp[-1] if dp[-1] != -1 else dp[-2]
print((ans * 3) % mod)
# print(dp)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        String word = s.next();
        if(word.contains("A")&&word.contains("B")) System.out.println("Yes");
        else System.out.println("No");

    }

}




class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

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

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

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

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}

Measured memory_bytes: 25224
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    String[] data = br.readLine().split(" ");
    int[] a = new int[n];
    long[] counts = new long[n];
    for(int i = 0; i < n; i++) {
      a[i] = Integer.parseInt(data[i]) - 1;
      counts[a[i]]++;
    }

    long ans = 0;
    for(int i = 0; i < n; i++){
      if(counts[i] > 1){
        ans += (counts[i] * (counts[i] - 1)) / 2;
      }
    }
    for(int i = 0; i < n; i++){
      long count = counts[a[i]];
      if(count > 1){
        long add   = ((counts[a[i]] - 1) * (counts[a[i]] - 2)) / 2;
        long minus = (counts[a[i]] * (counts[a[i]] - 1)) / 2;
        System.out.println(ans - minus + add);
      } else {
        System.out.println(ans);
      }
    }
  }
}

Measured memory_bytes: 67072
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
 long long int i,j,k,n,m;
 double s;
 s=0.0;
 cin >> n >> k;
 long long int a[n],b[n];
 for(i=0;i<n;i++)
 {
  cin >> a[i];
  b[i]=a[i];
 }
 for(i=1;i<n;i++)
 a[i]+=a[i-1];
 m=a[k-1];
 j=k-1;
 for(i=k;i<n;i++)
 {
  if((a[i]-a[i-k])>m)
  {
   m=a[i]-a[i-k];
   j=i;
  }
 }
 for(i=j;i>(j-k);i--)
 s+=(double)(b[i]+1)/2;
 cout << std::fixed << std::setprecision(12) << s;
 return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
int main() {
    //freopen("datain.txt","r",stdin);
    int tot=0;
    int n;
    int a,b;
    cin>>n;
    for (int i=0;i<n;++i) {
        cin>>a>>b;
        tot++;
        tot+=(b-a);
    }
    cout<<tot<<endl;
    return 0;
}


Measured memory_bytes: 256
import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n=int(input())

S=[''.join(sorted(input())) for _ in range(n)]

c=collections.Counter(S)
ans=0
for i in c.values():
    if i==2:
        ans+=1
    elif i>2:
        ans+=cmb(i,2)
print(ans)

Measured memory_bytes: 20036
#include <cstdio>
#include <iostream>
#include <vector>

bool can_be_solved(std::vector<int>& data, int index, int current_remain)
{
    if(data.size() <= index) {
        return false;
    } else if(current_remain == data[index]) {
        return true;
    }
    return can_be_solved(data, index + 1, current_remain) ||
           can_be_solved(data, index + 1, current_remain - data[index]);
}

int main()
{
    int group_1_size, group_2_size, group_2_data;
    std::cin >> group_1_size;
    std::vector<int> data(group_1_size);
    for(int i = 0; i < data.size(); i++) {
        std::cin >> data[i];
    }

    std::cin >> group_2_size;
    for(int i = 0; i < group_2_size; i++) {
        std::cin >> group_2_data;
        if(can_be_solved(data, 0, group_2_data)) {
            puts("yes");
        } else {
            puts("no");
        }
    }
}

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

int main(){
	int N,M,l,r;
	cin >> N >> M;
	int lmin=0,rmax=N;
	for(int i=0;i<M;i++){
		cin >> l >> r;
		if(lmin<l){lmin=l;}
		if(rmax>r){rmax=r;}
	}
	if(rmax<lmin){
		cout << 0 << endl;
	}else{
		cout << 1+rmax-lmin << endl;
	}
	return 0;
}

Measured memory_bytes: 256
N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)

if K >= N
    puts 1 ; exit
end
if (N - K) % (K - 1) == 0
    puts (N - K) / (K - 1) + 1
else
    puts (N - K) / (K - 1) + 1 + 1
end

Measured memory_bytes: 8068
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    double ans=a[0];
    rep(i,n){
        ans = (double)(ans + a[i])/2;
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 3708
# coding: utf-8
# Your code here!
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
ans=0
s=[]
sum_a=0
for i in range(n-1):
    sum_a+=A[i]
    ans+=sum_a*A[i+1]
    #s.append(sum_a)
print(ans%mod)
"""
for i in range(len(A)-1):
    for j in range(i+1,len(A)):
        ans+=A[i]*A[j]
        
print(ans%mod)
"""

Measured memory_bytes: 31760