Submission #227752

#	Time	Username	Problem	Language	Result	Execution time	Memory
227752		AaronNaidu	Wiring (IOI17_wiring)	C++14	20 / 100	145 ms	52328 KiB

wiring

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

vector<pair<int, char> > allPoints;
ll dp[500][500];



ll sub2(vector<int> r, vector<int> b) {
    ll toRet = 0;
    if (r.size() >= b.size())
    {
        for (int i = 0; i < b.size(); i++)
        {
            toRet += b[i] - r[i];
        }
        for (int i = b.size(); i < r.size(); i++)
        {
            toRet += b[0] - r[i];
        }
        return toRet;
    }
    for (int i = 0; i < r.size(); i++)
    {
        toRet += b[i] - r[i];
    }
    for (int i = r.size(); i < b.size(); i++)
    {
        toRet += b[i] - r[r.size() - 1];
    }
    return toRet;
}

ll onlyOne(vector<int> r, int b) {
    ll toRet = 0;
    for (int i = 0; i < r.size(); i++)
    {
        toRet += abs(b - r[i]);
    }
    return toRet;
}

ll getDP(int fir, int las) {
    vector<int> reds;
    vector<int> blues;
    int firBlue, firRed, secBlue, secRed;
    firBlue = firRed = secBlue = secRed = -1;
    if (dp[fir][las] < 1000000000000000000)
    {
        return dp[fir][las];
    }
    for (int i = fir; i <= las; i++)
    {
        if (allPoints[i].second == 'b')
        {
            blues.push_back(allPoints[i].first);
            secBlue = i;
            if (firBlue == -1)
            {
                firBlue = i;
            }
        }
        else
        {
            reds.push_back(allPoints[i].first);
            secRed = i;
            if (firRed == -1)
            {
                firRed = i;
            }   
        }
    }
    if (blues.size() == 0 or reds.size() == 0)
    {
        return 1000000000000000000;
    }
    if (blues.size() == 1)
    {
        dp[fir][las] = onlyOne(reds, blues[0]);
        return dp[fir][las];
    }
    if (reds.size() == 1)
    {
        dp[fir][las] = onlyOne(blues, reds[0]);
        return dp[fir][las];
    }
    if (reds[reds.size() - 1] < blues[0])
    {
        return dp[fir][las] = sub2(reds, blues);
        return dp[fir][las];
    }
    if (blues[blues.size() - 1] < reds[0])
    {
        dp[fir][las] = sub2(blues, reds);
        return dp[fir][las];
    }
    for (int i = max(firRed, firBlue); i < min(secRed, secBlue); i++)
    {
        dp[fir][las] = min(dp[fir][las], getDP(fir, i) + getDP(i+1, las));
    }
    return dp[fir][las];
}

ll min_total_length(vector<int> r, vector<int> b) {
    ll toRet = 0;
    int rIndex = 0;
    int bIndex = 0;
    for (int i = 0; i < 500; i++)
    {
        for (int j = 0; j < 500; j++)
        {
            dp[i][j] = 1000000000000000000;
        }
        
    }
    
    while (rIndex < r.size() or bIndex < b.size())
    {
        if (rIndex == r.size())
        {
            allPoints.push_back({b[bIndex], 'b'});
            bIndex++;
        }
        else if (bIndex == b.size())
        {
            allPoints.push_back({r[rIndex], 'r'});
            rIndex++;
        }
        else if (b[bIndex] < r[rIndex])
        {
            allPoints.push_back({b[bIndex], 'b'});
            bIndex++;
        }
        else
        {
            allPoints.push_back({r[rIndex], 'r'});
            rIndex++;
        }
    }
    toRet = getDP(0, allPoints.size() - 1);
    return toRet;
}

Compilation message (stderr)

wiring.cpp: In function 'll sub2(std::vector<int>, std::vector<int>)':
wiring.cpp:14:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < b.size(); i++)
                         ~~^~~~~~~~~~
wiring.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = b.size(); i < r.size(); i++)
                                ~~^~~~~~~~~~
wiring.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < r.size(); i++)
                     ~~^~~~~~~~~~
wiring.cpp:28:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = r.size(); i < b.size(); i++)
                            ~~^~~~~~~~~~
wiring.cpp: In function 'll onlyOne(std::vector<int>, int)':
wiring.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < r.size(); i++)
                     ~~^~~~~~~~~~
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (rIndex < r.size() or bIndex < b.size())
            ~~~~~~~^~~~~~~~~~
wiring.cpp:118:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (rIndex < r.size() or bIndex < b.size())
                                 ~~~~~~~^~~~~~~~~~
wiring.cpp:120:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (rIndex == r.size())
             ~~~~~~~^~~~~~~~~~~
wiring.cpp:125:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if (bIndex == b.size())
                  ~~~~~~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45