akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <array>
#include <vector>
#include <utility>
#include <bitset>
#include <queue>

using namespace std;

typedef long long ll;

constexpr ll MAX_K = 1000;

ll N, K;
ll   m[2 * MAX_K][2 * MAX_K][2];
ll  dp[2 * MAX_K][2 * MAX_K][2];
ll vdp[2 * MAX_K][2 * MAX_K][2];
ll hdp[2 * MAX_K][2 * MAX_K][2];

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

    for (ll i = 0; i < N; i++) {
        ll x, y;
        char c;
        cin >> x >> y >> c;
        m[x % (2 * K)][y % (2 * K)][(c == 'W') ? 0 : 1]++;
    }

    for (ll c = 0; c < 2; c++) {
        for (ll x = 0; x < 2 * K; x++) {
            for (ll y = 0; y < 2 * K; y++) {
                if (y == 0) {
                    for (ll yy = 0; yy < K; yy++) {
                        vdp[x][y][c] += m[x][yy][c];
                    }
                    continue;
                }

                vdp[x][y][c] = vdp[x][y - 1][c] + m[x][(y + K - 1) % (2 * K)][c] - m[x][y - 1][c];
            }
        }
    }

    for (ll c = 0; c < 2; c++) {
        for (ll y = 0; y < 2 * K; y++) {
            for (ll x = 0; x < 2 * K; x++) {
                if (x == 0) {
                    for (ll xx = 0; xx < K; xx++) {
                        hdp[x][y][c] += m[xx][y][c];
                    }
                    continue;
                }

                hdp[x][y][c] = hdp[x - 1][y][c] + m[(x + K - 1) % (2 * K)][y][c] - m[x - 1][y][c];
            }
        }
    }

    for (ll x = 0; x < K; x++) {
        for (ll c = 0; c < 2; c++) {
            dp[0][0][c] += vdp[x][0][c];
        }
    }

    for (ll c = 0; c < 2; c++) {
        for (ll x = 0; x < 2 * K; x++) {
            if (x != 0) {
                dp[x][0][c] = dp[x - 1][0][c] + vdp[(x + K - 1) % (2 * K)][0][c] - vdp[(x - 1) % (2 * K)][0][c];
            }

            for (ll y = 1; y < 2 * K; y++) {
                dp[x][y][c] = dp[x][y - 1][c] + hdp[x][(y + K - 1) % (2 * K)][c] - hdp[x][(y - 1) % (2 * K)][c];
            }
        }
    }

    ll ans = 0;
    for (ll x = 0; x < 2 * K; x++) {
        for (ll y = 0; y < 2 * K; y++) {
            ll sum = 0;
            ll xx = (x + K) % (2 * K);
            ll yy = (y + K) % (2 * K);
            sum += dp[x][y][0];
            sum += dp[xx][yy][0];
            sum += dp[xx][y][1];
            sum += dp[x][yy][1];
            if (ans < sum) {
                ans = sum;
            }
        }
    }

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



Measured memory_bytes: 250240
#include<stdio.h>
#include<stdlib.h>

#define N 1000

int main(){
  int key,i,j,n,A[N];
    scanf("%d",&n);
    if(n>100)exit(1);
    
    for(i=0;i<n;i++){
      scanf("%d",&A[i]);
      printf("%d",A[i]);
      if(i<n-1)printf(" ");
    }
    printf("\n");
for(j=1;j<=n-1;j++){
    key=A[j];
    i=j-1;
    while(i>=0&&A[i]>key){
        A[i+1]=A[i];
        i=i-1;
        A[i+1]=key; 
    }
    for(i=0;i<n;i++){
	  printf("%d",A[i]);
	  if(i<n-1)printf(" ");
        }
	printf("\n");
        
 }
 return 0;
}



Measured memory_bytes: 2064
#include "bits/stdc++.h"
#define M 1000000007
using namespace std;
typedef long long ll;
ll dp[101][100005];
ll sum[101][100005];
int main()
{

    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    for (int i = 0; i <= k; i++)
    {
        dp[0][k] = 0L;
    }
    for (int i = 0; i <= n; i++)
    {
        dp[i][0] = 1L;
        sum[i][0] = 1L;
    }
    for (int i = 0; i <= k; i++)
    {
        sum[0][i] = ((i == 0) ? dp[0][0] : sum[0][i - 1] + dp[0][i]);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            if (v[i] < j)
            {
                dp[i][j] = (sum[i - 1][j] % M - sum[i - 1][j - v[i] - 1] % M + M) % M;
            }
            else
            {
                dp[i][j] = sum[i - 1][j] % M;
            }
            sum[i][j] = (sum[i][j - 1] % M + dp[i][j] % M) % M;
        }
    }
    ll ans = dp[n][k];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 158080
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n;
  cin >> n;
  double t,a;
  cin >> t >> a;
  vector<int>h(n);
  rep(i,n) cin >> h.at(i);
  double mi = 100010;
  double k;
  int num=0;
  rep(i,n){
    k = abs(a - (t - h.at(i) * 0.006));
    if(k < mi){
      num = i;
      mi = min(k,mi);
    }
  }
  cout << num+1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL << 60; //intじゃ扱えないことに注意！
#define mod 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++) //範囲外参照とループの初期化に注意！

int main() {
  ll K,N;
  vector<ll> A(N);
  cin >> K >> N;
  rep(i,N) cin >> A[i];

  ll ans = 0;
  vector<ll> d(N);
  for(int i = 0; i < N-1; i++){
      d[i] = A[i+1]-A[i];
  }
  d[N-1] = K - A[N-1] + A[0];

  for(int i = 0; i < N; i++){
      ans = max(ans,d[i]);
  }
  
  cout << K - ans << endl;
}


Measured memory_bytes: 51072
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <vector>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
using namespace std;
int a[1][110];
int main(){
int n;
int ans=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[0][i];
for(int i=0;i<n;i++)
cin>>a[1][i];
int c=0;
for(int i=0;i<n;i++)
{
for(int b=i;b>=0;b--)
c+=a[0][b];
for(int j=i;j<n;j++)
{
c+=a[1][j];
}
ans=max(ans,c);
c=0;}
cout<<ans;
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i=0; i<(n); ++i)
#define per(i,n) for(int i=n-1;i>=0;++i)
#define rep1(i,n) for(int i=1; i<=n; ++i)
#define per1(i,n) for(int i=n; i>=1; ++i)
#define debug cout << "line : " << __LINE__ << " debug" << endl
#define Dcout(N) cout << setprecision(20) << N << endl
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF 1e9
#define MOD 1000000007
typedef long long ll;
//------------------------------------------------------------------------



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


  string s; cin >> s;
  if(s[2]==s[3] && s[4]==s[5]) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;cin>>n;
	string s;cin>>s;
	int l = 0;
	int r = n-1;
	int res = 0;
	while(l<r){
		while(l<n && s[l]=='R')l++;
		while(r>=0 && s[r]=='W')r--;
		if(l<r){
			swap(s[r],s[l]);
			res++;		
		}
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 3688
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm> // sort
#include <iomanip>
#include <queue>
#include <map>
#include <bits/stdc++.h>

using namespace std;

#define DEBUG 0
#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll INF = 1000000000000000000LL;
typedef pair<int,int> pint;

const int MOD = 1000000007;


int main(){

#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    string a,b,c;
    cin >> a >> b >> c;

    string res;

    if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0])res = "YES";
    else res = "NO";

    cout << res << endl;

    return 0;     
}



Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
//#include<cstdio>//"scanf("%lf",&(double));printf("%f",(double));"
//#include<iomanip>//"cout<<fixed<<setprecision(n)<<sth<<endl;"
//#include<string>//"reverse(s's it,s's it)"
//#include<functional>//"greater<T>" "sort(a,a+n,greater<int>());""
//#include<cmath>//"abs" "sqrt"
//#include<numeric>//"accumulate(inputit,inputit,init,(optional) object)"
//#include<algorithm>//"lower_bound(it,it,v)" "next_permutation(a,a+n)"
//"reverse(v's it,v's it)"(v: vector)
//#include<cassert>//"assert(cond);": error if cond doesn't hold.
using namespace std;
#define pb push_back//also for STRING
#define fi first
#define sc second
#define mp make_pair
#define is insert//also use as v.is(v's it,w's it,w's it);//Be careful in topcoder
#define ps push//stack,(priority) queue,//Be careful in topcoder.
#define fr front//queue//for priority, use top().//Be careful in topcoder.
typedef long long ll;//not necessarily//Be careful in topcoder.
typedef pair<int,int> pii;//Be careful in topcoder.
//Add other types in the same way.
const ll M=1000000007;//can be changed
int mod(int a){	return (a+M)%M;	}//M can be a variable
void plmod(ll &a,ll b){	a=(a+b+M)%M;	return;	}
void mnmod(ll &a,ll b){	a=(a-b+M)%M;	return;	}
void mlmod(ll &a,ll b){	a=(a*b)%M;  	return;	}
//Caution! you may need sth larger than "+M"!
void chmax(int &a,int b){	a=max(a,b);	return;	}
void chmin(int &a,int b){	a=min(a,b);	return;	}
//These 2 could be better in long long

int main(){
	int a,b,x;
	scanf("%d%d%d",&a,&b,&x);
	if(x>=a&&x<=a+b) printf("YES\n");
	else printf("NO\n");
	
}

Measured memory_bytes: 256
N = int(input())
a = [int(i) for i in input().split()]

import heapq

front = [a[i] for i in range(N)]
heapq.heapify(front)
middle = list(a[N:2*N])
back = list(a[2*N:3*N])

sumfront = [0 for _ in range(N+1)]
sumfront[0] = sum(list(a[0:N]))
for i in range(1,N+1):
    sumfront[i] = sumfront[i-1] + middle[i-1] \
    - heapq.heappushpop(front,middle[i-1]) 

minusmiddle = [-1*middle[i] for i in range(N)]
minusback = [-1*a[i+2*N] for i in range(N)]
heapq.heapify(minusback)
sumback = [0 for _ in range(N+1)]
sumback[N] = -1*sum(list(a[2*N:3*N]))
for i in range(N-1,-1,-1):
    sumback[i] = sumback[i+1] + minusmiddle[i] - heapq.heappushpop(minusback,minusmiddle[i])

ans = -1*float('inf')
for i in range(N+1):
    ans = max(ans,sumfront[i] + sumback[i])
print(ans)

Measured memory_bytes: 37212
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
   int W, H, N;
   cin >> W >> H >> N;
   int left = 0, right = W, bottom = 0, top = H;

   for(int i=0; i<N; i++) {
      int x, y, a;
      cin >> x >> y >> a;

      if(a == 1) {
         left = max(left, x);
      }
      else if(a == 2) {
         right = min(right, x);
      }
      else if(a == 3) {
         bottom = max(bottom, y);
      }
      else if(a == 4) {
         top = min(top, y);
      }
   }
   if(left >= right || bottom >= top) {
      cout << 0 << endl;
      return 0;
   }
   cout << (right - left) * (top - bottom ) << endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false)
#define ll long long
string s;
int vs[200000],a[200000];
int main()
{
        IO;
        int i, j=0, n, m, k=1, l=0, r, t,x,y,mx; ll sum=1;
        cin>>n>>m;
        for(i=1; i<=n; i++){
            cin>>a[i];
        }
        for(i=1; i<=m; i++)
           {
               cin>>k>>l;
               if(a[k]<=a[l]) vs[k]=1;
               if(a[l]<=a[k]) vs[l]=1;
           }
        for(i=1; i<=n; i++)
            if(vs[i]==0) j++;
        cout<<j<<endl;
    return 0;
}


Measured memory_bytes: 4444
#include <bits/stdc++.h>
using namespace std;
int main() {
  
  //必要な箱を用意
  int A;  //500円の枚数
  int B;  //100円の枚数
  int C;  //50円の枚数
  int Aim; //目標の金額
  int sum; //合計金額
  int count = 0; //何通りあるか
  
  //入力部
  cin >> A;
  cin >> B;
  cin >> C;
  cin >> Aim;
  
  for (int i = 0; i < A+1; i++){
    sum = 0; //初期化
    sum = 500*i;
    if (sum == Aim){
      count++;
      break;
    }
    if (sum > Aim)
      break;
    
    for (int j = 0; j < B+1; j++){
      sum = 0;
      sum = 500*i + 100*j;
      if (sum == Aim){
      count++;
      break;
      }
     if (sum > Aim)
      break;
      
      for (int k = 0; k < C+1; k++){
        sum = 0;
      	sum = 500*i + 100*j +50*k;
        if (sum == Aim){
      	count++;
      	break;
        }
        if (sum > Aim)
          break;
      }
    }
  }
  
  cout << count <<endl;//出力部
}

Measured memory_bytes: 3564
v, e = map(int, input().split())
data = []
for i in range(e):
    data.append(list(map(int, input().split())))

from collections import deque

q = deque(sorted(data, key=lambda x: x[2]))


parent = [i for i in range(v)]
rank = [0 for i in range(v)]

# Union-Find  ---------------
def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]

def judge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return True
    else:
        return False

def merge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return
    else:
        if rank[a_parent] > rank[b_parent]:
            parent[b_parent] = a_parent
        elif rank[a_parent] < rank[b_parent]:
            parent[a_parent] = b_parent
        else:
            parent[a_parent] = b_parent
            rank[b_parent] += 1

#----------------------------


ans = 0
while len(q) > 0:
    a = q.popleft()
    if not judge(a[0], a[1]):
        merge(a[0], a[1])
        ans += a[2]

print(ans)


Measured memory_bytes: 29340
#include <iostream>

bool solve(int i, int m, int A[], int n){
    if(m == 0){
        return true;
    }
    if(i >= n){
        return false;
    }
    return (solve(i+1, m, A, n)==true||solve(i+1, m-A[i], A, n)==true)?true:false;
}

int main(){
    int n;
    std::cin >> n;
    int A[n];
    for(int i=0; i<n; i++){
        std::cin >> A[i];
    }
    int q;
    std::cin >> q;
    int m[q];
    for(int i=0; i<q; i++){
        std::cin >> m[i];
    }
    bool k[q];
    for(int i=0; i<q; i++){
        if(solve(0, m[i], A, n)) std::cout << "yes\n";
        else  std::cout << "no\n";
    }
    return 0;
}


Measured memory_bytes: 3092
n = int(input())
x = [[int(i) for i in input().split()] for i in range(n)]
y = [x[0]]
for j in range(1,n):
	y.append([x[j][0]-x[j-1][0],abs(x[j][1]-x[j-1][1]),abs(x[j][2]-x[j-1][2])])
if all(k[0]>=k[1]+k[2] and k[0]%2==(k[1]+k[2])%2 for k in y): print("Yes")
else: print("No")

Measured memory_bytes: 33000
// template
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<long long, long long> LP;
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define REP_AB(i, a, b) for (ll i = ll(a); i < ll(b); i++)
#define REP_IN(i, n, x) for (ll i = 0; i < n; i++)in>>x;
#define REP_OUT(i, n, x) for (ll i = 0; i < n; i++)out<<x<<endl;
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)), v.end());
#define SIZE(x) ((ll)(x).size())
#define REVERSE(v) reverse(ALL(v))
// true / false
#define BIN_SEARCH(v, a) binary_search(ALL(v), a)
// index
#define BIN_LEFT(v, a) (lower_bound(ALL(v), a) - v.begin())
#define BIN_RIGHT(v, a) (upper_bound(ALL(v), a) - v.begin())
#define BIN_INSERT(v, a) (v.insert(v.begin() + BIN_LEFT(v, a), a))
#define DEL(v, i) v.erase(v.begin() + i)
#define INSERT(v, i, a) v.insert(v.begin() + i, a)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a / gcd(a, b)) * b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
#define out cout
#define in cin
#define endl '\n'
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
// template end
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    /*
    vector<ll> X(N);
    string s,t;
    in >> s >> t;
    vector<string> s,t;
    s.resize(N);
    ll N;
    in >> N;
    */

    ll X,Y;
    in >> X>>Y;

    if(X*4<Y){
        out << "No" << endl;
    }else if(Y%2==1){
        out << "No" << endl;
    }else if(X*2>Y){
        out << "No" << endl;
    }else{
        out << "Yes" << endl;
    }

    
    

    
    
}

Measured memory_bytes: 3644
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n, m;
int x[100100], y[100100];

vector<int> G[100100];
int dp[100100];

int calc(int v) {
    if (dp[v] < 0) {
        dp[v] = 0;
        for (int i = 0; i < (int)G[v].size(); i++) {
            int w = G[v][i];
            dp[v] = max(dp[v], calc(w)+1);
        }
    }
    return dp[v];
}

int solve() {
    for (int i = 0; i < m; i++) {
        G[y[i]].push_back(x[i]);
    }
    memset(dp, -1, sizeof(dp));

    for (int i = 0; i < n; i++) {
        if (dp[i] < 0)
            calc(i);
    }

    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, dp[i]);
    return res;
}

void input() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    input();
    cout << solve() << endl;
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

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

    if (K == 0) {
        cout << (ll)N * N << endl;
        return 0;
    }

    ll ans = 0;
    for (int b = K + 1; b <= N; ++b) {
        ans += N / b * (b - K);

        if (K <= N % b) ans += N % b - (K - 1);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

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

  if (M % N == 0)
    return !printf("%jd\n", M/N);

  std::vector<intmax_t> div;
  for (intmax_t i=1; i*i<=M; ++i) {
    if (M % i == 0) {
      div.push_back(i);
      if (i != M/i)
        div.push_back(M/i);
    }
  }
  std::sort(div.begin(), div.end());

  intmax_t res=1;
  for (intmax_t a_i: div) {
    if (N*a_i > M) break;
    res = std::max(res, a_i);
  }
  printf("%jd\n", res);
}


Measured memory_bytes: 256
N, A, B = map(int, input().split())

def find_sum_of_digits(n):
  s = str(n)
  sum = 0
  #Stringに変換桁数を数える

  for i in range(0,len(str(n))):
    sum = sum + int(s[i])
  return sum

total = 0
for number in range(1,N+1):
  all_sum = find_sum_of_digits(number)
  if A <= all_sum and all_sum <= B:
    total = total + number

print(total)
   
    

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod         1000000007
#define inf         1000000000000000000LL
#define vl          vector<ll>
#define F           first
#define S           second
#define db          long double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define all(x)      x.begin(),x.end()
#define pi          3.14159265358979323



void solve()
{
       string s;
       cin>>s;
       ll n = (s[0]-'0')*10 + (s[1]-'0');
       ll m = (s[2]-'0')*10 + (s[3]-'0');
       if((n==0 && m==0) || (n>12 && m>12))
       {
              cout<<"NA\n";
              return;
       }
       if(n==0)
       {
              if(m>12) { cout<<"NA\n"; return; }
              cout<<"YYMM\n";
              return;
       }
       if(m==0)
       {
              if(n>12) { cout<<"NA\n"; return; }
              cout<<"MMYY\n";
              return;
       }
       if(n<=12 && m<=12)
       {
              cout<<"AMBIGUOUS\n";
              return;
       }
       if(n>12)
       {
              cout<<"YYMM\n";
              return;
       }
       if(m>12)
       {
              cout<<"MMYY\n";
              return;
       }
}

int main()
{
       speed_up;
       ll T=1;
       //cin>>T;
       while(T--) solve();
	return 0;
}


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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , "; logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

const lint mod = MOD;
class mint{
    public:
        long long x;

    constexpr mint(long long _x = 0) : x((_x%mod+mod)%mod) {}
    constexpr mint operator-() const{
        return mint(-x);
    }
    constexpr mint& operator+=(const mint& a){
        if((x += a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator-=(const mint& a){
        if((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator*=(const mint& a){
        (x *= a.x) %= mod;
        return *this;
    }
    constexpr mint operator+(const mint& a) const{
        mint res(*this);
        return res+=a;
    }
    constexpr mint operator-(const mint& a) const{
        mint res(*this);
        return res-=a;
    }
    constexpr mint operator*(const mint& a) const{
        mint res(*this);
        return res*=a;
    }
    constexpr mint pow(long long x) const{
        if(!x) return 1;
        mint a = pow(x>>1);
        a *= a;
        if(x&1) a *= *this;
        return a; 
    }
    constexpr mint inv() const{
        return pow(mod-2);
    }
    constexpr mint& operator/=(const mint& a){
        return (*this) *= a.inv();
    }
    constexpr mint operator/(const mint& a) const{
        mint res(*this);
        return res/=a;
    }
    friend istream& operator>>(istream& is, mint& m){
        long long x; is >> x; m = x;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x; return os;
    }
};

int main(){
    mint n,k; cin>>n>>k;
    mint ans = (n-k+2)*((n+1)*(n+k+1)/2+1)-(n+1)*(n+2)*(n*2+3)/6+(k-1)*k*(k*2-1)/6;
    out(ans);
}

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

struct data
{
	long n;
	long c;
};

int main()
{
	struct data s[3];
	long k;
	rep(i, 3)
		cin >> s[i].n;
	cin >> k;
	s[0].c = 1;
	s[1].c = 0;
	s[2].c = -1;
	long sum = 0;
	rep (i , 3)
	{
		// cout << sum << endl;
		if (s[i].n < k)
		{
			sum += s[i].n * s[i].c;
			k -= s[i].n;
		}
		else
		{
			sum += s[i].c * k;
			break;
		}
		if (k == 0)
			break;
	}
	cout << sum;
	return (0);
}


Measured memory_bytes: 3644
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<float.h>
#define ERROR -1
#define MIN -2000000300
#define MAX 20000200
typedef long ll;
typedef struct
{
  ll x,y,z;
} Coordinates;

Coordinates Tree[MAX];//binary heap 
int Index;            //the size of a heap

int getParent(int i){ return i/2; }

int getLeft(int i)  { return 2*i; }

int getRight(int i) { return 2*i+1; }

void setValue(Coordinates *coor, ll x, ll y, ll z)
{
  coor->x = x;
  coor->y = y;
  coor->z = z;
}

void swap(Coordinates *a,Coordinates *b)
{
  Coordinates h = *a;
  *a = *b;
  *b = h;
}

// a > b
bool Compare(const Coordinates a,const Coordinates b)
{
  //?????????????????????????即????
  return a.x > b.x;
}


void maxHeapify(int i)
{
  int Left = getLeft(i);
  int Right = getRight(i);
  int largest;
 
  if(Left <= Index && Compare(Tree[Left],Tree[i]) ) largest = Left;
  else                                              largest = i;

  if(Right <= Index && Compare(Tree[Right],Tree[largest]) ) largest = Right;

  if(largest != i)
    {
      swap(&Tree[i],&Tree[largest]);
      maxHeapify(largest);
    }
}

int heapIncreaseKey(int i,Coordinates key)
{
  if(Compare(Tree[i],key))return ERROR;
  Tree[i] = key;
 
  while(i > 1 && Compare(Tree[i],Tree[getParent(i)]))
    {
      swap(&Tree[i],&Tree[getParent(i)]);
      i = getParent(i);
    }
}

Coordinates heapExtractMax()
{
  assert(Index >= 1);//heap underflow
  Coordinates Max = Tree[1];
  Tree[1] = Tree[Index];
  Index--;
  maxHeapify(1);
  return Max;
}

void add_node(Coordinates value)
{
  Coordinates dummy;
  setValue(&dummy,MIN,MIN,MIN);
  Tree[++Index] = dummy;
  heapIncreaseKey(Index,value);
}


int main()
{
  char op[1000];
  //double x,y,z;
  ll x;

  while(1){
    scanf("%s",op);
    if(strcmp(op,"insert") == 0){
      scanf("%ld",&x);
      Coordinates input;
      setValue(&input,x,MIN,MIN);
      add_node(input);
    }
    else if(strcmp(op,"extract") == 0){
      Coordinates output = heapExtractMax();
      printf("%ld\n",output.x);
      //printf("%ld\n",heapExtractMax());
    }
    else if(strcmp(op,"end") == 0)break;
  }
 
  return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//typedef vector<vector<ll>> Graph;

const ll mod = 1e9 + 7;
//const ll mod = 998244353;

#define REP(i,n) for(ll i=0;i<(ll)n;i++)
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define spa << " " <<
#define fi first
#define se second

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<endl;}};
template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0];
for(ll i=1;i<n;i++)cerr spa v[i];
cerr<<endl;};

string num2bit(ll num, ll len){
    string bit = "";
    REP(i, len){
    bit += char('0'+(num>>i & 1));
    }
    return bit;
}

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

    ll X;
    cin >> X;
    ll L = (X * 360)/gcd(X, 360);

    cout << L/X << endl;    

    return 0;
}

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

int main()
{
    int n;
    string s;
    cin >> n >> s;
    rep(i, s.size())
    {
        int y = 0;
        y = s[i] - 'A';
        s[i] = 'A' + (y + n) % 26;
    }
    cout << s << endl;

    return 0;
}


Measured memory_bytes: 256
N = gets.chomp.to_i
s = gets.chomp

ans = 0

[*'0'..'9'].repeated_permutation(3) do |i,j,k|
  a = s.index(i,0)
  b = s.index(j, a+1) if a
  c = s.index(k, b+1) if b

  ans += 1 if a && b && c
end

p ans


Measured memory_bytes: 3836
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int A = sc.nextInt();
		int B = sc.nextInt();

		sc.close();

		int ans = Math.abs(A - B);

		if (ans % 2 == 0) {
			out.println(Math.max(A, B) - ans / 2);
		} else {
			out.println("IMPOSSIBLE");
		}

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}


Measured memory_bytes: 21844
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rep3(var, min, max) for (ll (var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll (var) = (max) - 1; (var) + 1 > (min); --(var))
#define Mp(a,b) make_pair((a),(b))
#define F first
#define S second
#define CIN(s) int (s);cin>>(s);
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll MOD = 1e9 + 7;
ll INF =1e18;
ll PowMod_RepeatSquaring(ll N, ll P, ll M){
    if(P==0) return 1;
    if(P%2==0){
        ll t = PowMod_RepeatSquaring(N, P/2, M);
        return t*t % M;
    }
    return N * PowMod_RepeatSquaring(N, P-1, M);
}
ll pow1(ll x, ll n) { //x^n 計算量O(logn)
	ll ans = 1;
	while (n > 0) {
		if ((n & 1) == 1) {
			ans = ans * x;
			ans%=MOD;
		}
		x = x * x; //一周する度にx, x^2, x^4, x^8となる
		n >>= 1; //桁をずらす n = n >> 1
	}
	return ans;
}
long long modMult(long long a, long long b, long long m) {
  long long res = 0;
  long long exp = a % m;
  while (b) {
    if (b & 1) {
      res += exp;
      if (res > m) res -= m;
    }
    exp <<= 1;
    if (exp > m) exp -= m;
    b >>= 1;
  }
  return res;
}
long long powMod(long long a, long long b, long long m) {
  long long res = 1;
  long long exp = a % m;
  while (b) {
    if (b & 1) res = modMult(res, exp, m);
    exp = modMult(exp, exp, m);
    b >>= 1;
  }
  return res;
}
int main() {
    ll m,n;
    cin>>m>>n;
    cout<<powMod(m,n,MOD)<<endl;
}


Measured memory_bytes: 3072
S = list(input())

for i in range(len(S)):
    S[i] = int(S[i])

A = [S[len(S)-1]]
mod = 2019
for i in range(1,len(S)):
    A.append((S[len(S)-i-1]*pow(10,i,mod)+A[i-1]) % mod)

from collections import  Counter

c = Counter(A)

ans = c[0]

for i in range(0,2019):
    if c[i] >= 2:
        ans += (c[i]*(c[i]-1)) //2

print(ans)

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

using namespace std;

typedef long long int ll;

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

  int h, w;
  cin >> w >> h;
  vector < pair < int, int > > v;
  for(int i = 0; i < w; i++){
    int p;
    cin >> p;
    v.push_back({p, 0});
  }
  for(int i = 0; i < h; i++){
    int q;
    cin >> q;
    v.push_back({q, 1});
  }

  sort(v.begin(), v.end());
  ll x = h + 1, y = w + 1;
  ll total_wt = 0;
  for(int i = 0; i < h + w; i++){
    if(v[i].second == 0){
      total_wt += x * v[i].first;
      y--;
    }else{
      total_wt += y * v[i].first;
      x--;
    }
  }

  cout << total_wt << '\n';
}


Measured memory_bytes: 2420
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#include<map>
#include<iostream>
#include<cmath>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;


int main(){
   int R;
   cin >> R;
   cout << 2*R*M_PI << endl;
}

Measured memory_bytes: 3756
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = 2147483647;
const ld PI = 3.14159265358979323846;

//------------↓------------- M -------------- E ---------------- M --------------- O ---------------↓--------------//
// コンパイル 
// g++ -std=c++1z
//
// -------型変換--------
// int を string に変換
// string s = to_string(n);
// string を int に変換
// int n = stoi(s);
//
// -------二分探索---------
// k以上の値が最初に現れる時のイテレータ
// lower_bound(data.begin(), data.end(), k)
// kより大きい値が最初の現れる時のイテレータ O(logN)
// upper_bound(data.begin(), data.end(), k)
// kがdataに存在するかをtrue or falseで返す O(logN)
// binary_search(data.begin(), data.end(), k)
// 
//
//
//
//
//
// 
//------------↑------------- M -------------- E ---------------- M --------------- O ---------------↑--------------//






int main(void) {

    string S, T; cin >> S >> T;

    int n = S.size();
    bool flag = true;
    rep(i,n) {
        if (S[i] != T[i]) flag = false;
    }
    if (flag) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    
    
    return 0;
}




















Measured memory_bytes: 3620
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    char[] S = scanner.next().toCharArray();
    int res = 0;
    for (char ch : S) {
      switch (ch) {
        case '+':
          res++;
          break;
        case '-':
          res--;
          break;
      }
    }
    System.out.println(res);
  }
}


Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
int W,H,SX,SY,GX,GY,ice_N;
int field[14][14],ice[14][14],icelife[1000];
bool flag[14][14];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
void dfs(int x, int y);
bool iddfs(int x, int y, int c);
int main(){
  while(cin >>W>>H,W||H){
    for(int i=0; i<14; i++){for(int j=0; j<14; j++){field[i][j] = 1;flag[i][j] = true;}}
    memset(ice,0,sizeof(ice));
    memset(icelife,0,sizeof(icelife));
    ice_N = 1;
    string s;
    int ans;
    for(int i=1; i<=H; i++){
      cin >>s;
      for(int j=1; j<=W; j++){
	if(s[j-1] == '.'){field[j][i] = 0;}
	if(s[j-1] == '#'){field[j][i] = 1;}
	if(s[j-1] == 'X'){field[j][i] = 2;}
	if(s[j-1] == 'S'){field[j][i] = 0;SX = j;SY = i;}
	if(s[j-1] == 'G'){field[j][i] = 0;GX = j;GY = i;}
      }
    }
    for(int i=1; i<=W; i++){
      for(int j=1; j<=H; j++){
	if(field[i][j] == 2 && ice[i][j] == 0){
	  dfs(i,j);
	  icelife[ice_N]/=2;
	  ice_N++;
	}
      }
    }
    for(ans = abs(SX-GX)+abs(SY-GY);;ans++){
      if(iddfs(SX,SY,ans)){cout <<ans<<endl;break;}
    }
  }
  return 0;
}
void dfs(int x, int y){
  ice[x][y] = ice_N;
  icelife[ice_N]++;
  for(int i=0; i<4; i++){
    int p = x+dx[i],q = y+dy[i];
    if(field[p][q] == 2 && ice[p][q] == 0){dfs(p,q);}
  }
}
bool iddfs(int x, int y, int c){
  bool f = false;
  if(x == GX && y == GY){return true;}
  if(c<abs(x-GX)+abs(y-GY)){return false;}
  for(int i=0; i<4; i++){
    int p = x+dx[i],q = y+dy[i];
    bool next = false;
    for(int j=0; j<4; j++){
      int pp = p+dx[j],qq = q+dy[j];
      if(pp!=x||qq!=y){if(!flag[pp][qq]){next = true;}}
    }
    if(next){continue;}
    if(flag[p][q]){
      if(field[p][q] == 0){
	flag[p][q] = false;
	if(iddfs(p,q,c-1)){f = true;}
	flag[p][q] = true;
      }
      if(field[p][q] == 2){
	if(icelife[ice[p][q]]>0){
	  flag[p][q] = false;
	  icelife[ice[p][q]]--;
	  if(iddfs(p,q,c-1)){f = true;}
	  icelife[ice[p][q]]++;
	  flag[p][q] = true;
	}
      }
    }
  }
  return f;
}

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

int main(){
    string s;cin>>s;
    int k;cin>>k;
    set<string> sub; 
    for(char c='a';c<='z';c++){
        for(int i=0;i<s.size();i++){
            if(s[i]==c){
                string cc;
                cc=s[i];
                sub.insert(cc);
                for(int j=i+1;j<s.size();j++){
                    if(j-i>=5) break;
                    cc+=s[j];
                    sub.insert(cc);
                }
            }
        }
        if(sub.size()>=k) break;
    }
    vector<string> v(sub.begin(),sub.end());
    cout<<v[k-1]<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 1000000007
#define INF 98765431219876543
#define bitcnt(a) (ll) __builtin_popcount((a))
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<string, string> PS;

int main() {
  ll n;
  cin >> n;
  vector<ll> a, b, u, d;

  REP(i, n) {
    ll p;
    cin >> p;
    a.pb(p);
  }
  REP(i, n) {
    ll p;
    cin >> p;
    b.pb(p);
  }
  ll cnt = 0, c = 0;
  ;
  ll ans = 0;
  REP(i, n) {
    cnt += a[i] - b[i];
    if (a[i] - b[i] >= 0) {
      u.pb(a[i] - b[i]);
    } else {
      c += (a[i] - b[i]);
      ans++;
    }
  }

  if (cnt < 0) {
    cout << -1 << endl;
    return 0;
  }
  sort(u.begin(), u.end(), greater<ll>());

  REP(i, u.size()) {
    if (c >= 0)
      break;
    c += u[i];
    ans++;
    if (c >= 0)
      break;
  }

  cout << ans << endl;
}

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

using namespace std;
using namespace std::chrono;
        
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
        
#define print(a) {for(auto xxxxx : (a)) cout << xxxxx << ' '; cout << '\n';}
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

ll next(){ll x; cin >> x; return x;}
const int maxn = 3e5 + 5, intf = 2e9;
const ll inf = 1e18, mod = 998244353;
const ld eps = 1e-9;



void solve(){
  ll t1 = next()*60;
  t1 += next();
  ll t2 = next()*60;
  t2 += next();

  int k; cin >> k;
  cout << t2 - t1 - k << '\n';
}

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);
  
  for (int t = 1; t--;) {
    solve();
  }
        
  return 0;
}
/*

*/


Measured memory_bytes: 3544
#include<bits/stdc++.h>
using namespace std ;
typedef long long  ll;
const ll inf = 1e18 + 10;
const ll N = 2e5 + 10;
ll n , k ;
ll a[N], dp[N];
ll check(ll ind)
{
    ll mn = INT_MAX;
    if(ind == n)    return 0;
    if(dp[ind] != -1) return dp[ind];
    for(ll i = ind + 1 ; i <= min(ind + k , n) ; i ++)
    {
        mn =  min(mn , abs(a[ind] - a[i]) + check(i));
    }
    dp[ind] = mn;
    return mn;
}
void solve()
{
   cin >> n >> k;
   for(ll i = 1 ; i <= n ; i ++)    cin >> a[i];
   memset(dp , -1 , sizeof dp);
   cout << check(1);
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll t;
    t = 1;
    //cin >> t ;
    while(t --)
        solve();
    return 0;
}

Measured memory_bytes: 12212
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

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

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

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

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int N;
	cin >> N;
	vector< pair<int,int> > pos(2*N);
	for(int i=0;i<N;++i){
		cin >> pos[i].first;
		pos[i].second = 0;
	}
	for(int i=0;i<N;++i){
		cin >> pos[i+N].first;
		pos[i+N].second = 1;
	}
	//
	sort(pos.begin(), pos.end() );
	
	{
		LL ans = 1;
		LL num = 0;
		int kind = -1;
		for(int i=0;i<2*N;++i){
			if( kind == -1 ){
				kind = pos[i].second;
				num = 1;
			}
			else if( pos[i].second == kind ){
				++num;
			}else{
				ans = (ans * num) % MOD;
				--num;
				if( num == 0 ){
					kind = -1;
				}
			}
		}
		cout << ans << endl;
		return;
	}

	vector<int> A(2,0),need(2,0);
	vector<LL> fact(N+1,0);
	fact[1] = 1;
	for(LL i=2;i<=N;++i){
		fact[2] = (fact[i-1]*i) % MOD;
	}
	LL ans = 1;
	int prev = pos[0].second;
	++A[prev];
	for(int i=1;i<2*N;++i){
		int kind = pos[i].second;
		if( need[kind] ){
			--need[kind];
			continue;
		}
		if( prev == kind ){
			A[ kind ]++;
		}else{
			ans = ( ans * fact[ A[prev] ] ) % MOD;
			need[(kind+1)%2] += A[prev];
			A[prev] = 0;
			prev = kind;
		}
	}
	cout << ans << endl;
}

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

	solve();
}
#pragma endregion //main()


Measured memory_bytes: 1792
use std::io::prelude::*;

fn main() {
    let mut input_str = String::new();
    std::io::stdin().read_to_string(&mut input_str).unwrap();

    let input_parts = input_str.split_whitespace().collect::<Vec<_>>();
    let mut input_parts_it = input_parts.iter().cloned();
    let mut next = || input_parts_it.next().unwrap();

    let n: usize = next().parse().unwrap();
    let a: Vec<u64> = (0..n).map(|_| next().parse().unwrap()).collect();

    let mut a_sum = vec![0; a.len() + 1];

    let sum = (0..60u32)
        .map(|bit| {
            for i in 1..a.len() + 1 {
                a_sum[i] = a_sum[i - 1] + ((a[i - 1] >> bit) & 1);
            }

            let sum: u64 = (0..a.len() - 1)
                .map(|i| {
                    let j = i + 1..a.len();
                    let set_count = a_sum[j.end] - a_sum[j.start];
                    if (a[i] >> bit) & 1 != 0 {
                        (j.end - j.start) as u64 - set_count
                    } else {
                        set_count
                    }
                })
                .sum();

            (0..bit).fold(sum, |x, _| (x * 2) % 1000000007)
        })
        .fold(0, |x, y| (x + y) % 1000000007);

    println!("{}", sum);
}


Measured memory_bytes: 23796
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
using namespace std;
#define rep2(x,from,to) for(int x = (from); x < (to); ++(x))
#define rep(x,to) rep2(x,0,to)
#define MAX_N 1000
#define MAX_W 1000

// dp[i][j]???i????????\?????????????????????????????????j??\?????????????????????????????¨??????????????????????????§????????¨??????
int dp[MAX_N + 1][MAX_W + 1];

int main() {
	int W;
	int count = 1;
	while(cin >> W && W) {
		int n;
		cin >> n;
		int v[MAX_N], w[MAX_N];
		rep(i,n) {
			string s;
			cin >> s;
			string t;
			auto it = s.begin();
			for(; *it != ','; ++it) {
				t += *it;
			}
			v[i] = atoi(t.c_str());
			t = "";
			++it;
			for(; it != s.end(); ++it) {
				t += *it;
			}
			w[i] = atoi(t.c_str());
		}
		rep(i, MAX_N + 1) {
			rep(j, MAX_N + 1) {
				dp[i][j] = 0;
			}
		}
		rep2(i,1,n+1) {
			rep(j,W+1) {
				if(j < w[i - 1]) dp[i][j] = dp[i - 1][j];
				else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
			}
		}
		int ret = W;
		while(1) {
			if(dp[n][ret] != dp[n][ret - 1]) break;
			ret--;
		}
		cout << "Case " << count << ":" << endl;
		cout << dp[n][W] << endl;
		cout << ret << endl;
		count++;
	}
	return 0;
}

Measured memory_bytes: 5136
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.bigint, std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

void chmin(T)(ref T x, T y) { x = min(x, y); } void chmax(T)(ref T x, T y) { x = max(x, y); }
bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
T lcm(T)(T x, T y) { return x * (y / gcd(x, y)); }

long mod = 10^^9 + 7;
//long mod = 998_244_353;
//long mod = 1_000_003;
void moda(T)(ref T x, T y) { x = (x + y) % mod; }
void mods(T)(ref T x, T y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(T)(ref T x, T y) { x = (x * y) % mod; }
void modpow(T)(ref T x, T y) { if (!y) { x = 1; return; } auto t = x; x.modpow(y>>1); x.modm(x); if (y&1) x.modm(t); }
void modd(T)(ref T x, T y) { y.modpow(mod - 2); x.modm(y); }

void main()
{
	auto N = RD;
	
	auto arr = new long[](N+1);
	arr[] = 1;
	foreach (i; 2..N+1)
	{
		long x = i;
		while (x <= N)
		{
			++arr[x];
			x += i;
		}
	}

	long ans;
	foreach (i; 1..N+1)
	{
		ans += i * arr[i];
	}

	writeln(ans);
	stdout.flush;
	debug readln;
}


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
    return string(1, val);
}

int main() {
    ll N; cin >> N;
    vector<ll> ans(N+1);

    ans[0] = 0;
    for(ll i = 1; i <= N; ++i) {
        if(i % 3 == 0 && i % 5 == 0) {
            ans[i] = 0;
        } else if(i % 3 == 0) {
            ans[i] = 0;
        } else if(i % 5 == 0) {
            ans[i] = 0;
        } else {
            ans[i] = i;
        }
    }

    ll tmp = 0;
    for(int i = 0; i <= N; ++i) {
        tmp += ans[i];
    }
    cout << tmp << endl;
}

Measured memory_bytes: 11084
#include <stdio.h>
#include <math.h>

int main(void){
    double x1,x2,y1,y2,x,y;
    
    scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    x = x2 - x1;
    y = y2 - y1;
    
    printf("%lf\n" , sqrt(x*x+y*y));
    
    return 0;
}



Measured memory_bytes: 2104