akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define FILE
#define fr first
#define se second

using namespace std;

const long long N = 2e5 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

long long n;
long long m;
long long sum;
long long a[N];
int main()
{
    #ifdef FILEs
        freopen("input.txt", "r", stdin);
        /// freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    for(long long i = 1; i <= n; i ++){
        cin >> a[i];
        sum += a[i];
    }
    long long good = 1;
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    for(long long i = 1; i <= m; i ++){
        good &= ((a[i] * (4 * m)) >= sum);
    }
    if(good == 1){
        cout << "Yes\n";
    }
    else{
        cout << "No\n";
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	int n, m, i, j,flag=0,flagsave=0;
	string pstr[100],mstr[100];
	cin >> n;
	for (i = 0;i < n;i++) {
		cin >> pstr[i];
	}
	cin >> m;
	for (i = 0;i < m;i++) {
		cin >> mstr[i];
	}
	for (i = 0;i < n;i++) {
		for (j = 0;j < n;j++) {
			if (pstr[i] == pstr[j]) {
				flag++;
			}
		}
		for (j = 0;j < m;j++) {
			if (pstr[i] == mstr[j]) {
				flag--;
			}
		}
		if (flag > flagsave) {
			flagsave = flag;
		}
		flag = 0;
	}
	cout << flagsave << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int a, v, b, w, t;
  cin >> a >> v >> b >> w >> t;
  if (w >= v) {
    cout << "NO\n";
  } else {
    if ((ll)t * (v - w) >= abs(a - b)) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  } 
}



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


namespace ConsoleApplication52
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] a = new int[5];
            for (int b = 0; b < 5; b++)
                a[b] = int.Parse(Console.ReadLine());
            int c = 0;
            if (a[0] == 0)
                c += a[3];
            if (a[0] < 0)
            {
                c += (a[0] * -1) * a[2] + a[3];
                a[0] = 0;
            }
            c += (a[1] - a[0]) * a[4];
            Console.WriteLine(c);

        }
    }
}

Measured memory_bytes: 9060
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <fstream>
#include <cassert>
#include <ctime>
#include <list>
#include <numeric>
#include <iomanip>


using namespace std;
static const double EPS = 1e-6;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
#ifndef M_PI
const double M_PI=acos(-1);
#endif
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int((a).size()))
#define F first
#define S second
int dx[]={0,1,0,-1,1,1,-1,-1},dy[]={1,0,-1,0,1,-1,1,-1};

char in[10][10];

ll MOD = 100000007;
ll dp[2][1<<22];

vector<int> state;
int r,c;
void dfs(int dep,int cu){
  if(dep==c+1){
    state.pb(cu);
    return;
  }

  rep(i,3)
    dfs(dep+1,cu*4+i);
}

main(){

  cin >> r >> c;
  rep(i,r)rep(j,c){
    cin >> in[i][j];
    if(isdigit(in[i][j])) in[i][j]-='0';
    else in[i][j]=0;
  }

  dfs(0,0);
  
  int p=0;
  dp[0][0] = 1;
  rep(i,r)rep(j,c){
    //memset(dp[!p],0,sizoef(dp[!p]));
    FOR(it,state) dp[!p][*it]=0;
    p=!p;
    FOR(it,state){
      //cout << i << ' ' << j << ' ' << ' ' << *it << ' ' << dp[!p][*it] << endl;
      int up=(*it>>(2*c))&3;
      int left=(*it)&3;
      int ed=in[i][j];
      int cst = *it;
      if(j==0 && left) continue;
      if(ed && up+left>ed) continue;
      if(ed==0){
        if(up && left) continue;
        cst <<= 2;
        cst &= (1<<(c+1)*2)-1;
        cst &= ~15;        
        if(up) cst |= up<<2;
        else cst |= left;
        dp[p][cst] =(dp[p][cst]+dp[!p][*it])%MOD;
      }else{

        ed -= up+left;
        if(ed<0) continue;
        cst <<= 2;
        cst &= (1<<(c+1)*2)-1;
        cst &= ~15;
        for(int nleft=0;nleft<=min(2,ed);++nleft){
          if(ed-nleft>2) continue;
          int nst=cst;
          nst |= nleft|((ed-nleft)<<2);
          dp[p][nst] =(dp[p][nst]+dp[!p][*it])%MOD;
        }
      }
      
    }
  }

  cout << dp[p][0] << endl;
}

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

typedef long long ll;
#define endl '\n'

const int chessBoardSize = 8;
#define n chessBoardSize

int col[n], dig1[2*n], dig2[2*n];
int sol[n];
int ans[n];
bool exist[n];
bool found = false;

void search(int x){

    if(x==n){
        found=true;
        return;
    }

    if(exist[x]){
        search(x+1);
        return;
    }
    
    for(int y=0;y<n;y++){
        if(col[y] || dig1[y+x] || dig2[y-x+n-1])
            continue;
        sol[x]=y;
        col[y] = dig1[y+x] = dig2[y-x+n-1] = true;
        search(x+1);
        if(found)
            return;
        col[y] = dig1[y+x] = dig2[y-x+n-1] = false;
    }

}
int main() {
   
    std::ios::sync_with_stdio(false);

    int t, x, y;
    cin>>t;
    while(t--){
        cin>>x>>y;
        sol[x]=y;
        col[y] = dig1[y+x] = dig2[y-x+n-1] = true;
        exist[x]=true;
    }

    search(0);
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j!=sol[i])
                cout<<'.';
            else
                cout<<'Q';
        }
        cout<<endl;
    }
    
    return 0;
}



Measured memory_bytes: 3220
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <string.h>
#include <math.h>
typedef long long ll;
#define MAX(x, y)	(((x) > (y))? (x) : (y))
#define MIN(x, y)	(((x) < (y))? (x) : (y))
#define ABS(x)		(((x) < 0)? (-1*(x)) : (x))
#define REP(i,x,y)	for (int (i)=(x);(i)<(y);(i)++)
#define REP_(i,x,y)	for ((i)=(x);(i)<(y);(i)++)
#define MEMCLR(X)	memset((X),0,sizeof((X)))

using namespace std;
typedef pair<int, int> Point;
typedef vector<vector<Point>> Graph;

#define P 100
#define Q (P/2)

int N,D,X,S,a;


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

	REP(i,0,N) cin >> a,S+=(D-1)/a;
	S+=N + X;
	
	cout << S;

	return 0;
}


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

int main(){
    string a, b, c;
    cin >> a >> b >> c;
    if(a[a.length()-1] == b[0] && b[b.length()-1] == c[0]){
        cout << "YES";
    }else{
        cout << "NO";
    }
    return 0;
}

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

using namespace std;

long long int n,i;
long long int tablica[3003];
long long int visited[3003][3003];
long long int dp[3003][3003];

long long int licz(long long int lewy, long long int prawy)
{
    if(visited[lewy][prawy])
    {
        return dp[lewy][prawy];
    }
    visited[lewy][prawy]=true;
    if(lewy==prawy)
    {
        dp[lewy][prawy]=tablica[prawy];
        return dp[lewy][prawy];
    }
    dp[lewy][prawy] = max(tablica[lewy]-licz(lewy+1, prawy), tablica[prawy]-licz(lewy, prawy-1));
    return dp[lewy][prawy];
}

int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(i=0;i<n;i++){
        cin >> tablica[i];
    }
    cout << licz(0,n-1);
    return 0;
}


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

int main(void) {
  ios::sync_with_stdio(false);
  int A, B;
  cin >> A >> B;

  vector<vector<char>> answer(100, vector<char>(100));
  rep(i, 100) {
    rep(j, 100) {
      if (i < 50)
        answer[i][j] = '#';
      else
        answer[i][j] = '.';
    }
  }

  int out = 0;
  while (out / 2 != (A - 1)) {
    int y = (out / 100) * 2;
    int x = out % 100 + y % 2;
    answer[y][x] = '.';
    out += 2;
  }

  out = 0;
  while (out / 2 != (B - 1)) {
    int y = 51 + out / 100 * 2;
    int x = out % 100 + y % 2;
    answer[y][x] = '#';
    out += 2;
  }

  cout << "100 100" << endl;
  rep(i, 100) {
    rep(j, 100) { cout << answer[i][j]; }
    cout << endl;
  }
  return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    double v;
    while(cin>>v) {
        double y=v*v/19.6;
        int f;
        for(f=1; f*5-5<y; ++f);
        cout<<f<<'\n';
    }
    return 0;
}

Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
    string s;
    int start, end;
    start = end = -1;
    cin >> s;
    for (int i=0; i<s.size(); i++){
        if (s[i] == 'A' and start == -1 and end == -1)start = i;
        if (s[i] == 'Z' and start != -1)end=i;         
    }
    cout << end-start +1 << endl;
}

Measured memory_bytes: 640
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;
int main(){
    int s,a,b,c,d,e,f;
    cin>>s;

    a=s/1000;
    b=(s-(a*1000))/100;
    c=(s-(a*1000)-b*100)/10;
    d=(s-(a*1000)-b*100)%10;
    /*
    cout<<a<<endl;
    cout<<b<<endl;
    cout<<c<<endl;
    cout<<d<<endl;
    */
    e=a*10+b;
    f=c*10+d;
    
    if(e<=12&&e>=1){
        if(f<=12&&f>=1) cout<<"AMBIGUOUS"<<endl;
        else cout<<"MMYY"<<endl;
    }
    else{
        if(f<=12&&f>=1)cout<<"YYMM"<<endl;
        else cout<<"NA"<<endl;
        

    }
    return 0;
    
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
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 int long long

void solve() {
	int ans = 0;
    rep(i, 4) {
        char x; cin >> x;
        if(x == '2') ++ans;
    }
    cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define repin(a, n)  \
    vector<ll> a(n); \
    rep(i, n) { cin >> a[i]; }
#define repins(a, n)     \
    vector<string> a(n); \
    rep(i, n) { cin >> a[i]; }
#define repind(a, n)     \
    vector<double> a(n); \
    rep(i, n) { cin >> a[i]; }
#define in(a) \
    ll a;     \
    cin >> a;
#define ins(a) \
    string a;  \
    cin >> a;
#define ind(a) \
    double a;  \
    cin >> a;
template <class T>
inline void out(T a) {
    cout << a << endl;
}
inline void out(double a) { printf("%.10f\n", a); }
#define all(x)        (x).begin(), (x).end()    //昇順
#define rall(x)       (x).rbegin(), (x).rend()  //降順
#define rep2(i, a, b) for (ll i = (a); i < (b); ++i)
#define yes           out("Yes");
#define no            out("No");

int main() {
    in(xx);
    in(kk);
    in(d);

    __int128_t x = xx;
    __int128_t k = kk;

    if (x > 0) {
        if (x - d * k >= 0) {
            out((ll)(x - d * k));
        } else {
            ll a = abs(x - d * k) % d;
            ll b = abs(x - d * k) / d;
            if (b % 2 == 0) {
                out(a);
            } else {
                out(d - a);
            }
        }
    } else {
        if (x + d * k < 0) {
            out((ll)(abs(x + d * k)));
        } else {
            ll a = abs(x + d * k) % d;
            ll b = abs(x + d * k) / d;
            if (b % 2 == 0) {
                out(a);
            } else {
                out(d - a);
            }
        }
    }
}

Measured memory_bytes: 3580
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10


    x,k,d = LMIIS()

    absX = abs(x)
    # 0にできるだけ近づいて終わり
    if k*d <= abs(x):
        print(absX-k*d)
        return
    # マイナスにならない範囲でできるだけ0に近づく
    num = absX // d
    k -= num
    # 残りの移動回数が奇数なら、あと1回だけ移動する
    if k & 1:
        num += 1
    print(abs(absX-num*d))

     
    



    
main()

Measured memory_bytes: 65196
while 1:
    try:
        a, b, c = map(float, input().split())
        cnt1 = 0
        s1 = list(range(1, 11))

        s1.remove(a)
        s1.remove(b)
        s1.remove(c)
        for i in s1:
            if a + b + i <= 20:
                cnt1 += 1

        if cnt1 / 8 >= 0.5:
            print('YES')
        else:
            print('NO')

    except:
        break



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

#define copy(from, to) copy(from.begin(), from.end(), back_inserter(to));
#define sort(a) sort(a.begin(), a.end())

using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >>c;

  cout << max(c - (a - b), 0) << endl;
}

Measured memory_bytes: 256
n = int(input())

endA = 0
startB = 0
both = 0
cntAB = 0
for i in range(n):
    s = input()
    for j in range(len(s)-1):
        if s[j]=='A' and s[j+1]=='B':
            cntAB+=1
    if s[0] == 'B':
        startB +=1
    if s[-1] == 'A':
        endA += 1
    if s[-1]=='A' and s[0] == 'B':
        both+=1

onlyA = endA - both
onlyB = startB - both

if both:
    cntAB += both -1
    if onlyA:
        cntAB += 1
        onlyA -= 1
    if onlyB:
        cntAB +=1
        onlyB -= 1
    cntAB += min(onlyA,onlyB)
else:
    cntAB += min(onlyA,onlyB)
print(cntAB)


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

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

typedef pair<long long int, long long int> change;

bool pairCompare(const change& x, const change& y) {
	return x.second > y.second;
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<long long int> a(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}

	vector<change> bc(m);
	
	for (int i = 0; i < m; i++) {
		scanf("%d", &bc[i].first);
		scanf("%d", &bc[i].second);
	}

	sort(a.begin(), a.end());
	sort(bc.begin(), bc.end(), pairCompare);

	int prog = 0;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < bc[i].first; j++) {
			//if (prog < n) {
				if (a[prog] >= bc[i].second) break;
				a[prog] = bc[i].second;
				prog++;
			//}
		}
	}

	long long int ans = 0;
	/*
	for (auto itr = a.begin(); itr != a.end(); itr++) {
		ans += *itr;
	}*/

	for (int i = 0; i < n; i++) {
		ans += a[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

int main(void){
	string s;
	cin >> s;
	int l = INF, r = 0;
	rep(i, s.size()){
		if(s[i] == 'A') chmin(l, i);
		else if(s[i] == 'Z') chmax(r, i);
	}
	printf("%d\n", r - l + 1);
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<utility>
#include<map>
#include<deque>
#include<numeric>
#include<algorithm>
#include<unordered_map>
#include<cmath>

using namespace std;
using ll = long long int;
constexpr int INF = 1 << 29;
constexpr ll MOD = ll(1e9 + 7);

int n;
vector<int> c, s, f;

int time_in_next_station_from_now_time(int station, int now) {
	if (now < s[station])
		now = s[station];
	if (now % f[station] != 0)
		now += f[station] - now % f[station];
	return now + c[station];
}

int main(void) {
	cin >> n;
	n--;
	c = vector<int>(n);
	s = vector<int>(n);
	f = vector<int>(n);
	for (int i = 0; i < n; i++)
		cin >> c[i] >> s[i] >> f[i];

	vector<int> ret(n + 1, 0);
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++)
			ret[i] = time_in_next_station_from_now_time(j, ret[i]);
	}
	ret[n] = 0;
	for (int i = 0; i < n+1; i++)
		cout << ret[i] << endl;
	return 0;
}

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

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

bool is_black(char s){
    bool a = (s=='#');
    return a;
}

int main(void){
    int H,W;
    cin >> H >> W;
    vector<vector<char>>v(H,vector<char>(W));
    rep(i,H){
        rep(j,W){
            cin >> v[i][j];
        }
    }
    rep(i,H){
        rep(j,W){
            if (v[i][j]!='#')continue;
            bool flg=false;
            if(i!=0&&v[i-1][j]=='#')flg=true;
            if(j!=0&&v[i][j-1]=='#')flg=true;
            if(i!=H-1&&v[i+1][j]=='#')flg=true;
            if(j!=W-1&&v[i][j+1]=='#')flg=true;
            if (!flg){
                // cout << i  << " " << j << endl;
                cout << "No" << endl;
                return 0;
            }
            // cout << "i: " << i << "j: " << j << endl;
        }
        // printf("test\n");
    }
    // printf("test\n");

    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
//cout << fixed << setprecision(17) << res << endl;
const ll MOD = 1000000007;

int main() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    vector<set<ll>> d(26, set<ll>());
    for (ll i = 0; i < n ; ++i) {
        int c = s[i] - 'a';
        d[c].insert(i+1);
    }
    ll m;
    cin >> m;
    for (ll j = 0; j < m; ++j) {
        int com;
        cin >> com;
        if (com == 1) {
            ll i;
            int idx;
            char c;
            cin >> i >> c;
            idx = c - 'a';
            for (ll k = 0; k < 26; ++k) {
                d[k].erase(i);
            }
            d[idx].insert(i);
        } else {
            ll left, right;
            cin >> left >> right;
            ll count = 0;
            for (ll k = 0; k < 26; ++k) {
                auto iter = d[k].lower_bound(left);
                if (iter != d[k].end() && *iter <= right) {
                    ++count;
                }
            }
            cout << count << endl;
        }
    }
}


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

public class MainClass
{
	public const long Giri = 1000000007;

	public static void Main(string[] args)
	{
		var s = Console.ReadLine();
		
		const string str = "keyence";
		if(s == str || s.StartsWith(str) || s.EndsWith(str))
		{
			Console.WriteLine("YES");
			return;
		}
		
		int kstart = 0;
		while(kstart < s.Length)
		{
			int kindex = s.IndexOf('k', kstart);
			int keyIndex = 0;
			if(kindex == -1)
				break;
			for(int i = kindex; i < str.Length; i++)
			{
				if(keyIndex < str.Length && s[i] == str[keyIndex])
				{
					keyIndex ++;
				}
				else
				{
					if(kindex == 0 && s.EndsWith(str.Substring(keyIndex)))
					{
						Console.WriteLine("YES");
						return;
					}
					break;
				}
				
				if( keyIndex == str.Length - 1 && (kindex == 0 || kindex == s.Length - str.Length))
				{
					Console.WriteLine("YES");
					return;
				}
			}
			kstart = kindex+1;
		}
		Console.WriteLine("NO");
	}
	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}

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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	int a,b,c,x;
	cin >> a>> b >>c >> x;

	int ans = 0;
	for(int i = 0; i <= a; i++)
		for(int j = 0; j <= b; j++)
			for(int k = 0; k <= c; k++)
				if(500*i+100*j+50*k == x)
					ans++;

	cout << ans << endl;
	
	return 0;
}

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

stock_dp = [[0, 0] for _ in range(n+1)]
value_dp = [0] * (n + 1)

value_dp[0] = 1000
for i in range(1, n + 1):
    x = value_dp[i - 1]
    y = stock_dp[i - 1][0] + stock_dp[i - 1][1] * a[i - 1]
    if x > y:
        value_dp[i] = x
    else:
        value_dp[i] = y
    x = value_dp[i - 1] // a[i - 1] 
    y = stock_dp[i - 1][0] // a[i - 1] + stock_dp[i - 1][1]
    rx = value_dp[i - 1] % a[i - 1]
    ry = stock_dp[i - 1][0] % a[i - 1]
    if x > y:
        stock_dp[i][0] = rx
        stock_dp[i][1] = x
    elif x < y:
        stock_dp[i][0] = ry
        stock_dp[i][1] = y
    else:
        stock_dp[i][0] = max(rx, ry)
        stock_dp[i][1] = x
print(value_dp[n])

    

Measured memory_bytes: 62072
<?php

$input=trim(fgets(STDIN));

foreach(str_split($input) as $s){

	printf("%s",CharCheck($s)) . "\n";
}

function CharCheck($str){

	for($i=65;$i<65+26;$i++){

		if(chr($i)==$str){

			return chr($i+32);

		}

	}

	for($i=97;$i<97+26;$i++){

		if(chr($i)==$str){

			return chr($i-32);

		}

	}

	// ??§???????°?????????\????????????????????????
	return $str;


}

?>

Measured memory_bytes: 15268
N = int(input())
A_list = list(map(int,input().split()))
Q = int(input())
S = sum(A_list)
count_list = [0] * (10 ** 5 + 1)
for A in A_list:
    count_list[A] += 1 
for i in range(Q):
    B,C = map(int,input().split())
    S = S + count_list[B] * (C - B)
    count_list[C] += count_list[B]
    count_list[B] = 0
    print(S)
#    print(sum(A_list))

Measured memory_bytes: 83524
using System;
using System.Collections.Generic;
using System.Linq;

namespace AOJ_ICPC1 {
	struct Coo {
		public int x, y;
		public Coo(int _x, int _y) {
			x = _x; y = _y;
		}
		public void Move(Operation.Direction d) {
			switch (d) {
				case Operation.Direction.N: y++; break;
				case Operation.Direction.S: y--; break;
				case Operation.Direction.E: x++; break;
				case Operation.Direction.W: x--; break;
			}
		}
	}
	class Operation {
		public enum Direction{N, E, S, W};
		public Direction dir; 
		public int move;
		public Operation(char c, int m) {
			switch (c) {
				case 'N': dir = Direction.N; break;
				case 'E': dir = Direction.E; break;
				case 'S': dir = Direction.S; break;
				case 'W': dir = Direction.W; break;
			}
			move = m;
		}
	}
	class Program {
		static void Main(string[] args) {

			while (true) {
				int N = int.Parse(Console.ReadLine());
				if (N == 0) break;
				List<Coo> cooList = new List<Coo>();
				for (int n = 0; n < N; n++) {
					string[] str = Console.ReadLine().Split(' ');
					cooList.Add(new Coo(int.Parse(str[0]), int.Parse(str[1])));
				}
				int M = int.Parse(Console.ReadLine());
				Operation[] op = new Operation[M];
				for (int m = 0; m < M; m++) {
					string[] str = Console.ReadLine().Split(' ');
					op[m] = new Operation(str[0][0], int.Parse(str[1]));
				}
				

				Console.WriteLine(result(cooList, op)?"Yes":"No");
			}
		}

		static bool result(List<Coo> coolist, Operation[] op) {
			Coo pos = new Coo(10, 10);
			foreach (var o in op) {
				while (o.move > 0) {
					pos.Move(o.dir);
					o.move--;
					coolist.RemoveAll(c => c.x == pos.x && c.y == pos.y);
				}
			}
			return coolist.Count == 0;
		}
	}
}

Measured memory_bytes: 5600
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	a := getNextString(scanner)
	b := getNextString(scanner)
	c := getNextString(scanner)

	ab := oks(a, b)
	ba := oks(b, a)
	bc := oks(b, c)
	cb := oks(c, b)
	ac := oks(a, c)
	ca := oks(c, a)

	ans := len(a) + len(b) + len(c)
	// abc
	ans = minint(ans, ok(ab, bc, ac, len(a), len(b), len(c)))
	// acb
	ans = minint(ans, ok(ac, cb, ab, len(a), len(c), len(b)))
	// bac
	ans = minint(ans, ok(ba, ac, bc, len(b), len(a), len(c)))
	// bca
	ans = minint(ans, ok(bc, ca, ba, len(b), len(c), len(a)))
	// cab
	ans = minint(ans, ok(ca, ab, cb, len(c), len(a), len(b)))
	// cba
	ans = minint(ans, ok(cb, ba, ca, len(c), len(b), len(a)))
	fmt.Fprintln(writer, ans)
}
func ok(ab, bc, ac map[int]int, la, lb, lc int) int {
	ans := math.MaxInt32
	for i := 0; i < la; i++ {
		if ab[i] == 0 {
			continue
		}
		for j := 0; j < maxint(lb, la-i); j++ {
			if j < lb && bc[j] == 0 {
				continue
			}
			if i+j < la && ac[i+j] == 0 {
				continue
			}
			ans = minint(ans, maxint(la, maxint(lc+i+j, lb+i)))
		}
	}
	return ans
}
func oks(s, t string) map[int]int {
	n := len(s)
	m := len(t)
	ans := map[int]int{}
	for i := 0; i < n; i++ {
		valid := true
		for j := 0; valid && j < m && i+j < n; j++ {
			valid = valid && !(s[i+j] != '?' && t[j] != '?' && s[i+j] != t[j])
		}
		if valid {
			ans[i] = 1
		}
	}
	ans[n] = 1

	return ans
}
func maxint(a, b int) int {
	if a < b {
		return b
	}

	return a
}

func minint(a, b int) int {
	if a > b {
		return b
	}

	return a
}


Measured memory_bytes: 1152
#pragma region GNUC
//以下を参考にした
//https://yukicoder.me/wiki/auto_vectorization
#ifdef __GNUC__
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#endif
#pragma endregion

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>

#include <string>
#include <cstring>
#include <vector>
#include <valarray>
//#include <array>//x C++ (G++ 4.6.4)

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <cassert>//assert();
#include <fstream>
#include <random>
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)

/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#define PII pair<int,int>
/////////
using namespace::std;
#pragma region Math
// 最大公約数
template<class T>
inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;}
//inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}

// 最小公倍数
template<class T>
inline T lcm(T a, T b){return a / gcd(a, b) * b;}
//inline T lcm(T a, T b){return a * b / gcd(a, b);}

template<class T>
T pow(T x,int n){
	T mul = x;
	T ans = (T)1;
	while(n){
		if(n&1){
			ans *= mul;
		}
		mul *= mul;
		n >>= 1;
	}
	return ans;
}
#pragma endregion //math

void solve(){
	vector<string> str(3);
	for(int i=0;i<3;++i){
		cin >> str[i];
	}
	vector<int> pos(3,0);
	int turn = 0;
	while(true){
		if( pos[turn] >= str[turn].size() ){
			char ans = 'A'+turn;
			cout << ans;
			return;
		}
		int temp = turn;
		turn = str[temp][pos[temp]] - 'a';
		pos[temp]++;
	}
}

signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	//std::cout << std::fixed;//小数を10進数表示
	//cout << setprecision(16);//小数点以下の桁数を指定
	
	solve();
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;
const int MAX_L = 55;

ll buns[MAX_L];
ll paty[MAX_L];
ll total[MAX_L];

void init_burger()
{
    buns[0] = 0;
    paty[0] = 1;
    total[0] = 1;
    
    bool overflow = false;
    rep(i, 1, MAX_L)
    {
        paty[i] = (paty[i - 1] + 1) * 2  - 1;
        buns[i] = buns[i - 1] * 2  + 2;
        total[i] = paty[i] + buns[i];
    }
}

int main()
{
    init_burger();
    ll n, x;
    cin >> n >> x;

    int level_left = n;
    int level_now = n;
    ll ans = 0;

    while (x > 0)
    {
        ll num = total[level_now] + level_left - level_now;
        // cout << level_left << ' ' << level_now <<' ' << x << ' ' << num << ' ' << ans<< endl;

        if (num <= x)
        {
            x -= num;
            ans += paty[level_now];
            level_left = level_now;

            if (x > 0)
                --x, ++ans;
        }
        else
            --level_now;

        if (level_now < 0) break;
    }
    cout << ans << endl;
    return 0;
}

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

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    ll N,K;
    cin>>N>>K;
    vector<ll> P(N);
    vector<bool> same(N,false);

    REP(i,N){
        cin>>P[i];   
    }
    ll cnt=1;
    ll ans=0;
    REP(i,N-1){
        if(P[i+1]>P[i]) cnt++;
        else cnt=1;

        if(cnt>=K){
            same[i+1]=true;
            ans=1;
        }
    }

    vector<ll> dp(N+1,0);
    priority_queue<pair<ll,ll>> que1;
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> que2;
    if(same[K-1]) dp[K]=0;
    else dp[K]=1;
    REP(i,K){
        que1.push(make_pair(P[i],i));
        que2.push(make_pair(P[i],i));
    }
    REP2(i,K,N){
        dp[i+1]=dp[i];
        ll tmp1,tmp2;
        while(true){
            pair<ll,ll> p=que1.top();
            if(p.second<=i-K){
                que1.pop();
            }else{
                tmp1=p.first;
                break;
            }
        }

        while(true){
            pair<ll,ll> p=que2.top();
            if(p.second<i-K){
                que2.pop();
            }else{
                tmp2=p.first;
                break;
            }
        }

        if(!same[i]&&(P[i]<tmp1||P[i-K]>tmp2)){
            dp[i+1]++;
        }
        que1.push(make_pair(P[i],i));
        que2.push(make_pair(P[i],i));
    }
    ans+=dp[N];
    cout<<ans<<endl;
}

Measured memory_bytes: 12784
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <unordered_set>
#include <stack>
#include <algorithm>
#include <queue>
#include <ctime>
#include <iomanip>
#include <tuple>
#include <functional>
#include <map> 
#include <numeric> 

using namespace std;


#define ll long long
#define pi pair<int, int>
#define vi vector<int>
#define vp vector<pi>
#define msa(A, a, n) memset(A, a, n*sizeof(A))
#define msv(A, a) fill(A.begin(), A.end(), a);
#define msc(A, n) memset(A, '\0', n)
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define pern(i, b) per(i, b - 1, 0)
#define repn(i, b) rep(i, 0, b)
#define repe(i, a, b) for(int i = a; i <= b; i++)
#define repen(i, b) repe(i, 1, b)
#define fast ios_base::sync_with_stdio();cin.tie(0);
#define endl "\n"
//#define MYDEBUG	

void my_return(int code)
{
#ifdef MYDEBUG
	std::cout << "\n\nTime = " << fixed << std::setprecision(3) << double(clock()) / CLOCKS_PER_SEC << endl;
#endif
	exit(code);
}

int main()
{
	fast
#ifdef MYDEBUG
		freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int n, c = 0;
	cin >> n;
	
	repn(i, n) {
		int x, y;
		cin >> x >> y;

		if (x == y)c++;
		else c = 0;

		if (c == 3) break;
	}
	cout << ((c == 3) ? "Yes" : "No");


	my_return(0);
}


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

#define int long long

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

int n;

signed main() {
    int appear[26] = {};
    fill(appear, appear + 26, 100);
    cin >> n;
    for (int i = 0; i < n; i++) {
        string S;
        cin >> S;
        int cur_appear[26] = {};
        for (int j = 0; j < S.length(); j++) {
            cur_appear[S[j] - 'a']++;
        }
        for (int j = 0; j < 26; j++) {
            appear[j] = min(appear[j], cur_appear[j]);
        }
    }
    for (int i = 0; i < 26; i++) {
        if (appear[i] == 100) {
            continue;
        }
        for (int j = 0; j < appear[i]; j++) {
            cout << (char)(i + 'a');
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
flag = True
if N % 2 == 1:
  # 奇数個の場合、0,2,2,4,4,～みたいに並んでるはず
  if A[0] == 0:
    for i in range(1,N,2):
      if A[i] != i+1 or A[i+1] != i+1:
        flag = False
        break
    if flag: ans = 2**(N//2) % (10**9 + 7)

else:
  # 偶数個の場合、1,1,3,3,5,5,～のように並んでるはず
  if A[0] != 0:
    for i in range(0,N,2):
      if A[i] != i+1 or A[i+1] != i+1:
        flag = False
        break
    if flag: ans = 2**(N//2) % (10**9 + 7)
    
print(ans)  

Measured memory_bytes: 14008
#include<stdio.h>
#include<string.h>
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)<(y)?(y):(x))
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define INF 1000000000
int n;
int t[16][17];
int main(void){
    while(1){
        scanf("%d",&n);
        if(n==0) break;
        rep(i,n){
            rep(j,n+1){
                scanf("%d",&t[i][j]);
            }
        }
        int dp[1<<n];
        rep(i,(1<<n)) dp[i]=INF;
        dp[0]=0;
        for(int i=0;i<(1<<n);i++){
            for(int j=0;j<n;j++){
                if(!(i&(1<<j))){
                    int v=t[j][0];
                    for(int k=0;k<n;k++)
                        if(i&(1<<k))v=min(v,t[j][k+1]);
                    dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+v);
                }
            }
        }
        printf("%d\n",dp[(1<<n)-1]);
    }
}



Measured memory_bytes: 2068
import java.util.*;
import java.util.Map.Entry;
import java.math.*;
import java.awt.geom.*;
import java.io.*;
      
      
public class Main {		
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			if(n == 0) break;
			
			HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
			for(int i = 0; i < n; i++) {
				int tmp = sc.nextInt();
				if(i % 100000 == 0)System.gc();
				if(map.containsKey(tmp)) {
					map.put(tmp, map.get(tmp)+1);
					
				}
				else {
					map.put(tmp, 1);
				}
			}
			boolean ok = false;
			for(Entry<Integer,Integer> entry : map.entrySet()) {
				if(entry.getValue() > n/2) {
					System.out.println(entry.getKey());
					ok = true;
					break;
				}
			}
			if(!ok) {
				System.out.println("NO COLOR");
			}
		}
	}
 }

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

int gcd(int a, int b) {
  return b != 0 ? gcd(b, a%b) : a;
}
int lcm(int a, int b) {
  return a*b/gcd(a, b);
}

int a[1010];
signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, n) cin >> a[i];

  int r = lcm(n, m)/m, d=0, ret=0;
  REP(i, r) {
    int e = INF, f = -INF, cnt = 0;
    while(cnt<m) {
      e = min(e, a[d]);
      f = max(f, a[d]);
      ++d;
      if(d == n) d = 0;
      cnt++;
    }
    //cout << e << " " << f << endl;
    ret += f-e;
  }
  cout << ret << endl;
  return 0;
}

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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(a,b) for(int a=0;a<(b);++a)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
#define PI 3.14159265358979
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;
ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool compare_by_a(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}

vector<pair<int,ll>> vec[100000];
ll cost[100000];
void dfs(int now,ll COST){
    cost[now]=COST;
    int next;
    REP(i,vec[now].size()){
        next=vec[now][i].first;
        if(cost[next]<0){
            dfs(next,COST+vec[now][i].second);
        }
    }
}
int counter(int x){
    if(!x)return 0;
    return counter(x>>1)+(x&1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int> prime;
    prime.pb(2);
    int X;cin>>X;
    if(X==2){
        cout<<2<<endl;
        return 0;
    }
    for(int i=3;i<=1e7;i++){
        bool flg_p;flg_p=true;
        REP(j,prime.size()){
            if(i%prime[j]==0){
                flg_p=false;
                break;
            }
        }
        if(flg_p){
            prime.pb(i);
            if(i>=X){
                cout<<i<<endl;
                return 0;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
#define pival 3.14159265359
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pqq priority_queue
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl '\n'
ll power(ll x, ll y, ll p)
{ 
    ll res = 1;  
    x = x % p;
    while (y > 0) { 
        if (y & 1) res = (res * x) % p; 
        y = y >> 1;
        x = (x * x) % p;   
    } 
    return res; 
}
const ll L = 40;
string ss[L];
ll grid[L][L];
ll vis[L][L];
ll ans = 0;
ll h, w;
pll src;
struct node
{	
	ll x, y, dist;
};
ll bfs() {
	deque <node> q;
	node temp;
	temp.x = src.fi;
	temp.y = src.se;
	temp.dist = 0;
	vis[temp.x][temp.y] = 1;
	q.push_front(temp);
	while(!q.empty())
	{
		node p = q.front();
		q.pop_front();
		ans = max(ans, p.dist);
		ll i;
		if (p.x - 1 >= 0 && vis[p.x - 1][p.y] == 0 && grid[p.x - 1][p.y] == 1) {
			vis[p.x - 1][p.y] = 1;
			node temp = p;
			temp.x -= 1;
			temp.dist += 1;
			q.push_back(temp);
		}
		if (p.y - 1 >= 0 && vis[p.x][p.y - 1] == 0 && grid[p.x][p.y - 1] == 1) {
			vis[p.x][p.y - 1] = 1;
			node temp = p;
			temp.y -= 1;
			temp.dist += 1;
			q.push_back(temp);
		}
		if (p.x + 1 < h && vis[p.x + 1][p.y] == 0 && grid[p.x + 1][p.y] == 1) {
			vis[p.x + 1][p.y] = 1;
			node temp = p;
			temp.x += 1;
			temp.dist += 1;
			q.push_back(temp);
		}
		if (p.y + 1 < w && vis[p.x][p.y + 1] == 0 && grid[p.x][p.y + 1] == 1) {
			vis[p.x][p.y + 1] = 1;
			node temp = p;
			temp.y += 1;
			temp.dist += 1;
			q.push_back(temp);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);
 	cin >> h >> w;
 	for (ll i = 0; i < h; i++) cin >> ss[i];
 	for (ll i = 0; i < h; i++) {
 		for (ll j = 0; j < w; j++) {
 			if (ss[i][j] == '.') grid[i][j] = 1;
 		}
 	}
 	for (ll x1 = 0; x1 < h; x1++) {
 		for (ll y1 = 0; y1 < w; y1++) {
			if (grid[x1][y1] == 1) {
				for (ll i = 0; i < h; i++) {
					for (ll j = 0; j < w; j++) {
						vis[i][j] = 0;
					}
				}
				src = {x1, y1};
				bfs();
 			}
 		}
 	}   
 	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  char s[210000];
  cin >> s;
  int a=strlen(s);
  reverse(s,s+a);
  bool gameover=false;
  int ans[210000];
  int i;
  for(i=0;i<=n;i++){
    ans[i]=-1;
  }
  int now=0;
  int current=0;
  while(now!=n && !gameover){
    bool tumi=true;
    for(i=m;i>=1;i--){
      if(s[now+i]=='0'){
        now+=i;
        ans[current]=i;
        tumi=false;
        current++;
        break;
      }
    }
    if(tumi){
      gameover++;
    }
  }
  if(gameover){
    cout << "-1";
    return(0);
  }
  reverse(ans,ans+n+1);
  for(i=0;i<=n;i++){
    if(ans[i]==-1) continue;
    cout << ans[i] << " ";
  }
  return(0);
}

Measured memory_bytes: 896
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    if m&1:
        k = (m>>1)+1
        for i in range(k):
            print(i+1,m+1-i)
        for i in range(k-1):
            print(m+2+i,2*m+1-i)
    else:
        k = m>>1
        for i in range(k):
            print(i+1,m+1-i)
        for i in range(k):
            print(m+i+2,2*m-i+1)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 70772